Order acceptance and scheduling in a two-machine flowshop

We study the order acceptance and scheduling problem in a two-machine flowshop. The firm receives a pool of orders before a planning period, each of which is characterized by revenue, processing times on machines 1 and 2, a due date, and a tardiness penalty. The firm seeks to decide on the orders to accept and schedule the accepted orders so as to maximize the total net revenue. We formulate the problem as mixed-integer linear programming models, and develop a heuristic and a branch-and-bound (B&B) algorithm based on some derived dominance rules and relaxation techniques. We assess the performance of the B&B algorithm and the heuristic via computational experiments. The computational results show that the B&B algorithm can solve problem instances with up to 20 jobs within a reasonable time while the heuristic is efficient in approximately solving large instances of the problem.     

Heuristics for operational fixed job scheduling problems with working and spread time constraints

Operational fixed job scheduling problems select a set of jobs having fixed ready and processing times and schedule the selected jobs on parallel machines so as to maximize the total weight. In this study, we consider working time and spread time constrained versions of the operational fixed job scheduling problems. The working time constraints limit the total processing load on each machine. The spread time constraints limit the time between the start of the first job and the finish of the last job on each machine. For the working time constrained problem, we present a filtered beam search algorithm that evaluates the promising nodes of the branch and bound tree. For the spread time constrained problem we propose a two phase algorithm that defines the promising sets for the first jobs and finds a solution for each promising set. The results of our computational tests reveal that our heuristic algorithms perform very well in terms of both solution quality and time.     

A multiple ant colony optimization algorithm for the capacitated location routing problem

The success of a logistics system may depend on the decisions of the depot locations and vehicle routings. The location routing problem (LRP) simultaneously tackles both location and routing decisions to minimize the total system cost. In this paper a multiple ant colony optimization algorithm (MACO) is developed to solve the LRP with capacity constraints (CLRP) on depots and routes. We decompose the CLRP into facility location problem (FLP) and multiple depot vehicle routing problem (MDVRP), where the latter one is treated as a sub problem within the first problem. The MACO algorithm applies a hierarchical ant colony structure that is designed to optimize different subproblems: location selection, customer assignment, and vehicle routing problem, in which the last two are the decisions for the MDVRP. Cooperation between colonies is performed by exchanging information through pheromone updating between the location selection and customer assignment. The proposed algorithm is evaluated on four different sets of benchmark instances and compared with other algorithms from the literature. The computational results indicate that MACO is competitive with other well-known algorithms, being able to obtain numerous new best solutions.     

Inventory control in a two-level supply chain with risk pooling effect

We consider an inventory control problem in a supply chain consisting of a single supplier, with a central distribution center (CDC) and multiple regional warehouses, and multiple retailers. We focus on the problem of selecting warehouses to be used among a set of candidate warehouses, assigning each retailer to one of the selected warehouses and determining replenishment plans for the warehouses and the retailers. For the problem with the objective of minimizing the sum of warehouse operation costs, inventory holding costs at the warehouses and the retailers, and transportation costs from the CDC to warehouses as well as from warehouses to retailers, we present a non-linear mixed integer programming model and develop a heuristic algorithm based on Lagrangian relaxation and subgradient optimization methods. A series of computational experiments on randomly generated test problems shows that the heuristic algorithm gives relatively good solutions in a reasonable computation time.     

A heuristic for balancing the inventory level of different locations through lateral shipments

Solving transshipment problems to optimality is difficult, unless several simplifying hypotheses are assumed (such as unit-sized customer demands and replenishments, negligible replenishment lead time, etc.). For this reason, some heuristics have been recently proposed in order to provide rules, which incorporate relevant factors of the problem, to find conditions under which it makes sense to transship a certain number of units from one retailer to another. Most of these studies concern emergency transshipment, which means that shipments between locations can occur only when a shortage happens, and shipments are assumed to be fast enough to satisfy the location in shortage. When this assumption is not feasible, as in many real cases, transshipments between locations have to be performed before a shortage happens. The paper addresses this case, which can be named ‘preventive’ transshipment, where the inventory level of different locations at the same echelon is balanced through lateral shipments, before a shortage happens. A heuristic for deciding on transshipment policy (when to transship and how much), trying to minimise overall expected costs, is presented. A simulation study considering different scenarios is performed and results confirm the effectiveness of the heuristic.     

An integrated multi-depot hub-location vehicle routing model for network planning of parcel service

The paper describes why optimal design of depot and hub transportation networks for parcel service providers makes it necessary to develop a generalized hub location and vehicle routing model (VRM). Analogous problems occur for postal, parcel and piece goods service providers. A generalized hub location and VRM is developed which encompasses the determination of the number, locations of hubs and depots and their assigned service areas as well as the routes between the demand points and consolidation points (depots, hubs). Because this task leads to a very complex transport design problem, a heuristic solution concept has to be developed. The applicability to a case study is demonstrated; the case of completely new system configuration for Austria is considered. Management must simultaneously decide the number, location, service areas and routes from demand points to depots and vice versa (the pickup and delivery structure) as well as the number and locations of hubs and the routes of depot–hub and hub–hub transports (the hub location or line haul structure), The developed management support decision model leads for real cases to a tremendous number of some million binary variables as well as continuous variables and million of constraints.     

Scheduling jobs with values dependent on their completion times

The paper concerns two scheduling problems with job values and losses of job values (costs) dependent on job completion times. In the first problem, we consider scheduling jobs with stepwise values in parallel processor environment. In the stepwise value, there is given a number of moments at which the job value decreases and between them the job value is constant (thus, the value deteriorates over time). The maximized criterion is the total job value. We prove strong NP-hardness of a single processor case of the problem and construct a pseudo-polynomial time algorithm for a special case with fixed number of unrelated parallel processors and fixed number of common moments of job value changes. Additionally, for uniform and unrelated parallel processors we construct and experimentally test several heuristic algorithms based on the list strategy. The second problem is a single processor one with piecewise linear losses of job values (the loss increases over time). The minimized criterion is the total loss of job value. We prove strong NP-hardness of the problem and existence of a pseudo-polynomial time exact algorithm for its special case. We also construct some heuristic algorithms for this problem and verify experimentally their efficiency.     

An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem

The inventory routing problem (IRP) addressed in this study is a many-to-one distribution network consisting of an assembly plant and many distinct suppliers where each supplies a distinct product. We consider a finite horizon, multi-periods, multi-suppliers and multi-products where a fleet of capacitated homogeneous vehicles, housed at a depot, transport products from the suppliers to meet the demand specified by the assembly plant in each period. The demand for each product is deterministic and time varying. A mathematical formulation of the problem is given and CPLEX 9.1 is run for a finite amount of time to obtain lower and upper bounds. A hybrid genetic algorithm, which is based on the allocation first route second strategy and which considers both the inventory and the transportation costs, is proposed. In addition to a new set of crossover and mutation operators, we also introduce two new chromosome representations. Several medium and small sized problems are also constructed and added to the existing data sets to show the effectiveness of the proposed approach.     

A local search algorithm for the optimization of the stochastic economic lot scheduling problem

This paper describes a model for the stochastic economic lot scheduling problem (SELSP) and a Local Search heuristic to find close to optimal solutions to this model. The SELSP considers multiple products, which have to be scheduled on a single facility with limited capacity and significant setup times and costs. The demand is modeled as a stationary compound renewal process. The objective is to find a schedule that minimizes the long-run average costs for setups and inventories while satisfying a given fill rate. We use a cyclic scheduling approach in which the individual cycle time of each product is a multiple of some basic period (fundamental cycle).For the deterministic version of the SELSP, efficient heuristics have been developed which guarantee the feasibility of the solution by adding an additional constraint to the problem. In our case this is not sufficient, because for the calculation of the average inventory levels and fill rates we need to develop a schedule with detailed timing of the lots. We present an efficient heuristic for this scheduling problem, which can also be used to check the feasibility of the solution. Thereby, the most time-consuming step (the calculation of average inventory levels and fill rates) is only performed for a limited set of candidates.The algorithm was tested on deterministic benchmark problems from literature and on a large set of stochastic instances. We report on the performance of the heuristic in both cases and try to identify the main factors influencing the objective.     

Multiple part-type scheduling in flexible robotic cells

This paper considers the scheduling problem arising in two-machine manufacturing cells which repeatedly produce a set of multiple part-types, and where transportation of the parts between the machines is performed by a robot. The cycle time of the cell depends on the robot move sequence as well as the processing times of the parts on the machines. For highly flexible CNC machines, the processing times can be adjusted. To this end, this study tries to find the robot move sequence as well as the processing times of the parts on each machine that jointly minimize the cycle time. The problem of determining the best cycle in a 2-machine cell is first modeled as a traveling salesman problem. Then, an efficient 2-stage heuristic algorithm is constructed and compared with the most common heuristic approach of longest processing time (LPT).     

An agent-based nurse rostering system under minimal staffing conditions

Nurse rostering is a complex problem. We propose a new heuristic using a competitive agent-based negotiation that focuses on nurse preferences called competitive nurse rostering (CNR). Unlike the existing literature, CNR models each nurse's preference functions separately and separates the cost minimization and preference maximization problems. CNR produces quality nurse rosters even though it cannot leverage extra staffing. As an agent system, CNR can distribute computational requirements over several computer systems, include other solution methods at various points in of the rostering problem, and act as a real-time scheduling system. These benefits are not naturally inherent in centralized heuristic solutions.     

An integrated distribution routing model in multi-supply center system

A distribution routing problem with time constraint is one of the important problems in distribution and supply center management. This research is concerned with an integrated distribution routing problem for multi-supply centers based on improved genetic algorithm and graphical user interface (GUI)-type programming. In this research, we proposed a method based on a three-step approach: in step 1 a sector clustering model is developed to transfer the multi-supply center problem to single supply center problems which are easier to be solved; in step 2 we developed a vehicle routing model with time constraints and in step 3 we developed a GA-TSP model which can improve the vehicle routing schedules. The objective of the problem is to minimize the logistic cost for a set of customers without being tardy or exceeding the capacity or travel time of the vehicles. For computational purpose, we developed a GUI-type computer program according to the proposed methods and the sample outputs show that the proposed method is very effective on a set of standard test problems, and it could be potentially useful in solving the distribution routing problems.     

Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families

Motivated by a bottleneck operation in a multi-layer ceramic capacitor production line, we study a scheduling problem of batch processing machine in which a number of jobs are processed simultaneously as a batch. The performance measures considered include makespan, total completion time, and total weighted completion time. We first present a new simple integer programming formulation for the problem, and using this formulation, one can easily find optimal solutions for small problems. However, since the problem is NP-hard and the size of a real problem is very large, we propose a number of heuristic algorithms and design a hybrid genetic algorithm to solve practical big-size problems in a reasonable computational time. To verify performance of the algorithms, we compare them with lower bounds for the problems. From the results of these computational experiments the heuristic algorithms including the genetic algorithm show different performances for the three problems.     

Two-stage flowshop earliness and tardiness machine scheduling involving a common due window

This paper studies a non-preemptive two-stage flowshop scheduling problem to minimize the earliness and tardiness under the environment of a common due window. The window size and the window location are considered to be given parameters. The just-in-time problem exists naturally and has many practical applications. The problem is shown to be NP-complete in the strong sense. We develop a branch and bound algorithm and a heuristic to solve the problem. We conduct the computational experiments to test the performances of the algorithms. A strong lower bound is derived for the branch and bound algorithm that can efficiently solve 15 jobs problem for about 5 minutes. The heuristic is shown to be efficient and effective, which can solve the problem of 150 jobs for about 20 seconds and provide near-optimal solution. We justify that the heuristic is an excellent solution approach for large problem instances. We also show that four special cases are either polynomial solvable or NP-complete in the ordinary sense.     

大型钢网架结构支撑卸载施工技术研究——以广东省佛冈体育馆工程为例

为了使网架结构在卸载过程中能平稳地进行应力重分布，保证结构的安全性及施工的便利性，结合佛冈体育馆钢网架屋面项目，采用有限元分析对临时支撑卸载过程进行施工模拟，分析卸载方案各个阶段结构的内力分布情况；建立屋面大型钢网架临时支撑的卸载方案，用于指导现场施工；在实际结构的关键支撑点位处，使用先进测量技术自动化监测采集支撑杆件卸载全过程的应力应变、位移变形等数据，与施工模拟结果进行对比分析。结果表明：卸载过程各关键杆件的最大变形和应力不存在超限情况，整体结构受力稳定。所提卸载工艺能够有效控制网架构件变形和内力，实现体育馆屋面的信息化施工管理，保证网架临时支撑体系平稳、安全卸载。研究成果可为优化网架结构支撑卸载方案提供借鉴，并为大跨度网架结构施工管理提供科学依据。     

A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems—A case study for solar cell industry

This paper studies a solar cell industry scheduling problem which is similar to the traditional hybrid flow shop scheduling (HFS). In a typical HFS with parallel machines problem, the allocation of machine resources for each order should be scheduled in advance and then the optimal multiprocessor task scheduling in each stage could be determined. However, the challenge in solar cell manufacturing is the number of machines can be dynamically adjusted to complete the job within the shortest possible time. Therefore, the paper addresses a multi-stage HFS scheduling problem with characteristics of parallel processing, dedicated machines, sequence-independent setup time, and sequence-dependent setup time. The objective is to schedule the job production sequence, number of sublots, and dynamically allocate sublots to parallel machines such that the makespan time is minimized. The problem is formulated as a mixed integer linear programming (MILP) model. A hybrid approach based on the variable neighborhood search and particle swarm optimization (VNPSO) is developed to obtain the near-optimal solution. Preliminary computational study indicates that the developed VNPSO not only provides good quality solutions within a reasonable amount of time but also outperforms the classic branch and bound method and the current industry heuristic practiced by the case company.     

A network approach to modeling the multi-echelon spare-part inventory system with backorders and interval-valued demand

A multi-echelon inventory system implies the existence of a hierarchy of stocking locations, and the dependence and interaction between them. We consider a multi-echelon, spare-part inventory management problem with outsourcing and backordering. The problem is characterized by deterministic repair time/cost, and supply and demand that lie within prescribed intervals and that vary over time. The objective is to minimize the total inventory and transportation costs. We develop a network model for problem analysis and present a network flow algorithm for solving the problem. We prove that the Wagner-Whitin property, known for the lot-sizing problem, can be extended to the spare-part inventory management problem under study.     

A mathematical model for a buffered two-stage manufacturing cell with an unreliable transfer device

In this paper, a mathematical model is developed for a manufacturing cell of two manufacturing stages with a single-storage buffer and a transfer robot for loading, unloading and moving parts into and out of the buffer. Both stages and the transfer robot are subject to failure. The cell is modeled as a random Markov process on the assumption that time to failure and time to repair are exponentially distributed. The output of such manufacturing cell is established, and as expected, it is less than that where the transfer means are continuously available.     

Synergistic valuations and efficiency in spectrum auctions

In spectrum auctions, bidders typically have synergistic values for combinations of licenses. This has been the key argument for the use of combinatorial auctions in the recent years. Considering synergistic valuations turns the allocation problem into a computationally hard optimization problem that generally cannot be approximated to a constant factor in polynomial time. Ascending auction designs such as the Simultaneous Multiple Round Auction (SMRA) and the single-stage or two-stage Combinatorial Clock Auction (CCA) can be seen as simple heuristic algorithms to solve this problem. Such heuristics do not necessarily compute the optimal solution, even if bidders are truthful. We study the average efficiency loss that can be attributed to the simplicity of the auction algorithm with different levels of synergies. Our simulations are based on realistic instances of bidder valuations we inferred from bid data from the 2014 Canadian 700 MHz auction. The goal of the paper is not to reproduce the results of the Canadian auction but rather to perform “out-of-sample” counterfactuals comparing SMRA and CCA under different synergy conditions when bidders maximize payoff in each round. With “linear” synergies, a bidder's marginal value for a license grows linearly with the total number of licenses won, while with the “extreme national” synergies, this marginal value is independent of the number of licenses won unless the bidder wins all licenses in a national package. We find that with the extreme national synergy model, the CCA is indeed more efficient than SMRA. However, for the more realistic case of linear synergies, SMRA outperforms various versions of CCA that have been implemented in the field including the one used in the Canadian 700 MHz auction. Overall, the efficiency loss of all ascending auction algorithms is small even with high synergies, which is remarkable given the simplicity of the algorithms.     

Two-machine flowshop scheduling with a truncated learning function to minimize the makespan

Scheduling with learning effects has continued to attract the attention of scheduling researchers. However, the majority of the research on this topic has been focused on the single-machine setting. Moreover, under the commonly adopted learning model in scheduling, the actual processing time of a job drops to zero precipitously as the number of jobs increases, which is at odds with reality. To address these issues, we study a two-machine flowshop scheduling problem with a truncated learning function in which the actual processing time of a job is a function of the job's position in a schedule and the learning truncation parameter. The objective is to minimize the makespan. We propose a branch-and-bound and three crossover-based genetic algorithms (GAs) to find the optimal and approximate solutions, respectively, for the problem. We perform extensive computational experiments to evaluate the performance of all the proposed algorithms under different experimental conditions. The results show that the GAs perform quite well in terms of both efficiency and solution quality.