Minimum deviation algorithm for two-stageno-wait flowshops with parallel machines

The scheduling problems studied in this paper concern the two-stage no-wait flowshops with parallel machines under the objective function of the minimization of the maximum completion time. A new heuristic algorithm, i.e., the minimum deviation algorithm, is developed to solve the problems. In order to evaluate the average case performance of the algorithm, we design numerical experiments to compare the effectiveness of the algorithm with that of the other approximation algorithms. Extensive simulations are conducted under different shop conditions, and the results statistically show that the minimum deviation algorithm performs well under most of the situations.     

Parallel-identical-machine job-shop scheduling with different stage-dependent buffering requirements

The neglect of buffering requirements in a classical job shop scheduling system often results in inapplicability in many complex real-world applications. To overcome this inapplicability, a new and more generalised scheduling problem is proposed under different stage-dependent buffering requirements and parallel use of identical-function machine units at each processing stage in job shop environments. The problem is formulated as a mixed integer programming model that can be exactly solved by ILOG-CPEX for small-size instances. Moreover, a hybrid metaheuristic algorithm embedded with a state-of-the-art constructive algorithm is developed. The computational experiment shows that the proposed metaheuristic can efficiently solve large-size instances. The result analysis indicates that the proposed approach can provide better configuration of real-world scheduling systems. The proposed DBPMJSS methodology has a potential to analyse, model and solve many industrial systems with the requirements of buffering conditions, particularly for manufacturing, railway, healthcare and mining industries.     

一个求解无等待流水调度问题混合算法

针对以总完工时间最小为目标的无等待流水调度问题提出一个启发式算法和禁忌搜索算法相结合的混合禁忌搜索算法HTS(Hybrid Taboo Search):以启发式算法产生的解作为初始解,通过禁忌搜索提高解的质量.实验结果表明:提出的HTS性能上优于经典的RC1、RC2、PH1(p)和DS算法.     

A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem

In this paper, a discrete particle swarm optimization (DPSO) algorithm is presented to solve the no-wait flowshop scheduling problem with both makespan and total flowtime criteria. The main contribution of this study is due to the fact that particles are represented as discrete job permutations and a new position update method is developed based on the discrete domain. In addition, the DPSO algorithm is hybridized with the variable neighborhood descent (VND) algorithm to further improve the solution quality. Several speed-up methods are proposed for both the swap and insert neighborhood structures. The DPSO algorithm is applied to both 110 benchmark instances of Taillard [Benchmarks for basic scheduling problems. European Journal of Operational Research 1993;64:278–85] by treating them as the no-wait flowshop problem instances with the total flowtime criterion, and to 31 benchmark instances provided by Carlier [Ordonnancements a contraintes disjonctives. RAIRO Recherche operationelle 1978;12:333–51], Heller [Some numerical experiments for an M×J$\mathrm{M}\times \mathrm{J}$ flow shop and its decision-theoretical aspects. Operations Research 1960;8:178–84], and Revees [A genetic algorithm for flowshop sequencing. Computers and Operations Research 1995;22:5–13] for the makespan criterion. For the makespan criterion, the solution quality is evaluated according to the reference makespans generated by Rajendran [A no-wait flowshop scheduling heuristic to minimize makespan. Journal of the Operational Research Society 1994;45:472–8] whereas for the total flowtime criterion, it is evaluated with the optimal solutions, lower bounds and best known solutions provided by Fink and Voß [Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research 2003;151:400–14]. The computational results show that the DPSO algorithm generated either competitive or better results than those reported in the literature. Ultimately, 74 out of 80 best known solutions provided by Fink and Voß [Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research 2003;151:400–14] were improved by the VND version of the DPSO algorithm.     

An efficient simple metaheuristic for minimizing the makespan in two-machine no-wait job shops

This paper examines the problem of scheduling two-machine no-wait job shops to minimize makespan. The problem is known to be strongly NP-hard. A two-phase heuristic is developed to solve the problem. Phase 1 of the heuristic transforms the problem into a no-wait flow shop problem and solves it using the well known Gilmore and Gomory algorithm. Phase 2 of the heuristic improves the solution obtained in phase 1 using a simple tabu search algorithm. Computational results show that the proposed heuristic performs extremely well in terms of both solution quality and computation time. It finds an optimal solution to about 90% of the problem instances and the average deviation from the lower bond for the other problem instances is infinitesimal.     

Makespan minimization in a no-wait flow shop problem with two batching machines

This paper deals with the problem of task scheduling in a no-wait flowshop with two batching machines. Each task has to be processed by both machines. All tasks visit the machines in the same order. Batching machines can process several tasks per batch so that all tasks of the same batch start and complete together. The batch processing time for the first machine is equal to the maximal processing time of the tasks in this batch, and for the second machine is equal to the sum of the processing times of the tasks in this batch. We assume that the capacity of any batch on the first machine is bounded, and that when a batch is completed on the first machine it is immediately transferred to the second machine. The aim is to make batching and sequencing decisions that allow the makespan to be minimized.     

A faster polynomial algorithm for 2-cyclic robotic scheduling

This paper addresses the 2-cyclic identical part scheduling in a no-wait robotic flowshop where exactly two parts enter and two parts leave the production line during each cycle. This problem was previously proved to be polynomially solvable in O(N⁸log N) time, where N is the number of tanks in the production line. This paper proposes an improved algorithm with reduced complexity O(N⁵log N).     

An improved heuristic to minimize total flow time for scheduling in the m-machine no-wait flow shop

In this paper, we present a constructive heuristic to minimize total flow time criterion for the well-known NP-hard no-wait flow shop scheduling problem. It is based on the assumption that the priority of a job in the initial sequence is given by the sum of its processing times on the bottleneck machines. The initial sequence of jobs thus generated is further improved using a new job insertion technique. We show, through computational experimentation, that the proposed method significantly outperforms the best-known heuristics while retaining its time complexity of O(n²). Statistical tests of significance are used to confirm the improvement in solution quality.     

Multiple response optimization using mixture-designed experiments and desirability functions in semiconductor scheduling

Today's highly competitive semiconductor markets place a great emphasis on responsiveness to customers. In the past, competition has primarily focused on the product design arena. More recently, short lead times and good on-time delivery performance have become equally important to winning customer satisfaction. To meet these criteria, a recent thrust of manufacturing management has focused on the use of effective scheduling techniques to manage wafer movement. Dabbas and Fowler (1999) proposed an approach that combines multiple dispatching criteria into a single rule with the objective of maximizing multiple response measures simultaneously. This is accomplished using a linear combination with relative weights. The weights identify the contribution of the different criteria. This paper details the use of experimental design methodology as well as a desirability function approach in the optimization of the weights' assignment to the different criteria. The basic idea of the desirability function approach is to transform a multi-response problem into a single-response problem by means of a mathematical transformation. The responses of interest are on time delivery, variance of lateness, mean cycle time and variance of cycle time. Results demonstrate that the proposed approach is superior to the use of single-dispatching criteria with an average of 20% improvement for all responses. All data presented in this paper have been normalized to disguise actual performance results as the raw data are considered to be Motorola confidential data.