Two-machine flow shop scheduling of polyurethane foam production

This paper studies a two-machine flow shop scheduling problem with a supporting precedence relation. The model originates from a real production context of a chemical factory that produces foam-rubber products. We extend the traditional two-machine flow shop by dividing the operations into two categories: supporting tasks and regular jobs. In the model, several different compositions of foam rubber can be mixed at the foam blooming stage, and products are processed at the manufacturing stage. Each job (product) on the second machine cannot start until its supporting tasks (parts) on the first machine are all finished and the second machine is not occupied. The objective is to find a schedule that minimizes the total job completion time. The studied problem is strongly NP-hard. In this paper, we propose a branch-and-bound algorithm incorporating a lower bound and two dominance rules. We also design a simple heuristic and an iterated local search (ILS) algorithm to derive approximate solutions. The performances of the proposed algorithms are examined through computational experiments.     

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.     

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.     

A unified solution approach for the due date assignment problem with tardy jobs

We analyze a number of due date assignment problems with the weighted number of tardy jobs objective and show that these problems can be solved in O(n²) time by dynamic programming. We show that the effects of learning or the effects of past-sequence-dependent setup times can be incorporated into the problem formulation at no additional computational cost. We also show that some single-machine due date assignment problems can be extended to an identical parallel machine setting. Finally, we improve the complexity of the solution algorithms for two other due date assignment problems.     

Algorithm portfolios for logistics optimization considering stochastic demands and mobility allowance

The vehicle routing problem with stochastic demand (VRPSD) is a well known NP-hard problem. The uncharacteristic behaviour associated with the problem enhances the computational efforts required to obtain a feasible and near-optimal solution. This paper proposes an algorithm portfolio methodology based on evolutionary algorithms, which takes into account the stochastic nature of customer demand to solve this computationally complex problem. These problems are well known to have computationally complex objective functions, which make their solutions hard to find, particularly when problem instances of large dimensions are considered. Of particular importance in such situations is the timeliness of the solution. For example, Apple was forced to delay their shipments of iPads internationally due to unprecedented demand and issues with their delivery systems in Samsung Electronics and Seiko Epson. Such examples illustrate the importance of stochastic customer demands and the timing of delivery. Moreover, most of the evolutionary algorithms, known for providing computationally efficient solutions, are unable to always provide optimal or near optimal solutions to all the VRPSD instances within allocated time interval. This is due to the characteristic variations in the computational time taken by evolutionary algorithms for same or varying size of the VRPSD instances. Therefore, this paper presents portfolios of different evolutionary algorithms to reduce the computational time taken to resolve the VRPSD. Moreover, an innovative concept of the mobility allowance (MA) in landmoves based on the levy’s distribution function has been introduced to cope with real situations existing in vehicle routing problems. The proposed portfolio approach has been evaluated for the varying instances of the VRPSD. Four of the existing metaheuristics including Genetic Algorithm (GA), Simulated Annealing (SA), Artificial Immune System (AIS), TABU Search (TS) along with new neighbourhood search, are incorporated in the portfolios. Experiments have been performed on varying dimensions of the VRPSD instances to validate the different properties of the algorithm portfolio. An illustrative example is presented to show that the set of metaheuristics allocated to certain number of processors (i.e. algorithm portfolio) performed better than their individual metaheuristics.     

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.     

Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine

This study deals with the problem of scheduling jobs on a single machine to minimize the mean absolute deviation of the job completion time about a large common due window subject to the maximum tardiness constraint. Using the well-known three-field notation, the problem is identified as MAD/large DueWindow/T_max. The common due window is set to be large enough to allow idle time prior to the beginning of a schedule to investigate the effect of the T_max constraint. Penalties arise if a job is completed outside the due window. A branch and bound algorithm and a heuristic are proposed. Many properties of the solutions and precedence relationships are identified. Our computational results reveal that the branch and bound algorithm is capable of solving problems of up to 50 jobs and the heuristic algorithm yields approximate solutions that are very close to the exact solution.     

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.     

Near-optimal (r,Q) policies for a two-stage serial inventory system with Poisson demand

We consider a two-stage serial inventory system whose cost structure exhibits economies of scale in both stages. In the system, stage 1 faces Poisson demand and replenishes its inventory from stage 2, and the latter stage in turn orders from an outside supplier with unlimited stock. Each shipment, either to stage 2 or to stage 1, incurs a fixed setup cost. We derive important properties for a given echelon-stock (r, Q) policy for an approximation of the problem where all states are continuous. Based on these properties, we design a simple heuristic algorithm that can be used to find a near-optimal (r, Q) policy for the original problem. Numerical examples are given to demonstrate the effectiveness of the algorithm.     

A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling

This paper addresses the multiobjective flexible job shop scheduling problem (MOFJSP) regarding minimizing the makespan, total workload, and maximum workload. The problem is solved in a Pareto manner, whose goal is to seek for the set of Pareto optimal solutions. We propose a multiobjective evolutionary algorithm, which utilizes effective genetic operators and maintains population diversity carefully. A main feature of the proposed algorithm is its simplicity—it needs only two parameters. Performance of our algorithm is compared with seven state-of-the-art algorithms on fifteen popular benchmark instances. Only our algorithm can find 70% or more non-dominated solutions for every instance.     

基于变邻域搜索算法的物流配送系统集成优化研究

本文针对物流配送系统集成优化问题,考虑取货和送货两种业务的配送情形下仓库和车辆的容量上限约束,构建包括仓库的开放成本、配送成本以及容量溢出成本的非线性混合整数优化模型,设计变邻域搜索启发式算法对模型进行求解。算法通过泰森多边形确定位置上的初始订单分配,再通过扫描半径及消费者数据结构标识实现邻域搜索,改进算法对解决方案进行迭代更新,完成优化求解。最后通过对辽宁宅急送取／送一体化物流配送案例进行数值分析,验证算法可行性和有效性。     

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.     

A coevolutionary algorithm for the flexible delivery and pickup problem with time windows

This paper addresses a flexible delivery and pickup problem with time windows (FDPPTW) and formulates the problem into a mixed binary integer programming model in order to minimize the number of vehicles and to minimize the total traveling distance. This problem is shown to be NP-hard. In this study, therefore, a coevolutionary algorithm incorporated with a variant of the cheapest insertion method is developed to speed up the solution procedure. The FDPPTW scheme overcomes the shortcomings of the existing schemes for the delivery and pickup problems. By testing with some revised Solomon's benchmark problems, the computational results have shown the efficiency and the effectiveness of the developed algorithm.     

A minimum cost flow model for level of repair analysis

Given a product design and a repair network for capital goods, a level of repair analysis determines for each component in the product (1) whether it should be discarded or repaired upon failure and (2) at which location in the repair network to do this. In this paper, we show how the problem can be modelled as a minimum cost flow problem with side constraints. Advantages are that (1) solving our model requires less computational effort than solving existing models and (2) we achieve a high model flexibility, i.e., many practical extensions can be added. Furthermore, we analyse the added value of modelling the exact structure of the repair network, instead of aggregating all data per echelon as is common in the literature. We show that in some cases, cost savings of over 7% can be achieved. We also show when it is sufficient to model the repair network by echelons only, which requires less input data.     

The relationship between supply chain factors and adoption of e-Collaboration tools: An empirical examination

We consider minimum-cost scheduling of different vehicle types on a predetermined set of one-way trips. Trips have predetermined ready times, deadlines and associated demands. All trips must be performed. The total time of operations on any vehicle is limited. We develop a mixed integer model to find the optimal number of vehicles at a minimum cost. Based on the hard nature of the problem, we propose six heuristics. Computational results reveal that heuristics return exceptionally good solutions for problem instances with up to 100 jobs in very small computation times, and are likely to perform well for larger instances.     

Metaheuristics for drilling operation scheduling in Taiwan PCB industries

Among all types of production environment, identical parallel machines are frequently used to increase the manufacturing capacity of the drilling operation in Taiwan printed circuit board (PCB) industries. Additionally, multiple but conflicting objectives are usually considered when a manager plans the production scheduling. Compared to the single objective problem, the multiple-objective version no longer looks for an individual optimal solution, but a Pareto front consisting of a set of non-dominated solutions will be needed and established. The manager then can select one of the alternatives from the set. This research aims at employing a variable neighborhood search (VNS) algorithm and a multiple ant colony optimization (MACO) algorithm to solve the identical parallel-machine scheduling problem with two conflicting objectives: makespan and total tardiness. In VNS, two neighborhoods are defined—insert a job to a different position or swap two jobs in the sequence. To save the computational expense, one of the neighborhoods is randomly selected for the target solution which is also arbitrarily chosen from the current Pareto front. In MACO, a two-phase construction procedure where three colonies are employed in each phase is proposed. These two algorithms are tested on a set of real data collected from a leading PCB factory in Taiwan and their performances are compared. The computational results show that VNS outperforms all competing algorithms—SPGA, MOGA, NSGA-II, SPEA-II, and MACO in terms of solution quality and computational time.     

A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system

We analyze a two-machine flow-shop scheduling problem in which the job processing times are controllable by the allocation of resources to the job operations and the resources can be used in discrete quantities. We provide a bicriteria analysis of the problem where the first criterion is to maximize the weighted number of just-in-time jobs and the second criterion is to minimize the total resource consumption cost. We prove that although the problem is known to be NP-hard even for constant processing times, a pseudo-polynomial time algorithm for its solution exists. In addition, we show how the pseudo-polynomial time algorithm can be converted into a two-dimensional fully polynomial approximation scheme for finding an approximate Pareto solution.     

Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multiprocessor tasks

This paper addresses the problem of multiprocessor task-scheduling in a hybrid flow shop (HFS) problem to minimize the makespan. Due to the complex nature of an HFS problem, it is decomposed into the following two sequential decision problems: determining the job permutation in stage 1, followed by a decoding method to assign jobs into each machine in subsequent stages when designing a heuristic algorithm. The decoding method plays a pivotal role for improving the solution quality of any algorithm for the HFS problem. However, the majority of existing algorithms ignores the problem and is only concerned with the first decision problem. This study emphasizes the importance of the decoding method via a small test, and searches for a number of solid decoding methods that can be incorporated into the cocktail decoding method. Then, this study develops a particle swarm optimization (PSO) algorithm that can be combined with the cocktail decoding method. In the PSO, a variety of job sequences are generated using the PSO procedure in stage 1, and the cocktail decoding method is used to assign the jobs to machines in sequential stages. Moreover, a modified lower bound is introduced. Computational results show that the proposed lower bound is competitive, and with the help of the cocktail decoding method, the proposed PSO, and even the adoption of a standard PSO framework, significantly outperforms the majority of existing algorithms in terms of quality of solutions, especially for large problems.     

Optimally locating in-house logistics areas to facilitate JIT-supply of mixed-model assembly lines

In modern-day production systems, ever-rising product variety poses a great challenge for the internal logistics systems used to feed mixed-model assembly lines with the required parts. As an answer to this challenge many manufacturers especially from automobile industries have identified the supermarket-concept as a promising part feeding strategy to enable flexible small-lot deliveries at low cost. In this context, supermarkets are decentralized in-house logistics areas in the direct vicinity of the final assembly line, which serve as intermediary stores for parts. Small tow trains are loaded with material in a supermarket and deliver parts Just-in-Time to the stations lying on their fixed route. This paper discusses the general pros and cons of the supermarket-concept and treats the decision problem of determining the optimal number and placement of supermarkets on the shop floor. A mathematical model is proposed, an exact dynamic programming algorithm presented, and the validity of the proposed approach for practical purposes as well as the trade-off resulting from fixed installation and maintenance cost is investigated in a comprehensive computational study.