A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> We consider the problem of scheduling no-wait jobs, with release dates and sequence dependent setup times, on a flow shop to minimize the makespan. We show that this problem is equivalent to the asymmetric traveling salesman problem with additional visiting time constraints. For this latter problem we give a mathematical formulation and two lower bounds. Two heuristic algorithms for solving the scheduling problem are proposed. Performance analysis of both lower bounds and heuristics on randomly generated test problems are carried out. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> We consider a problem of scheduling jobs in two-machine no-wait flow shops for which the objective is to minimize the makespan. Each job, upon completion of its processing on the first machine, must be transferred immediately to the second machine due to a no-wait in process constraint. Every job requires a setup time on each machine before it is processed. The setup on the second machine is anticipatory, since it can be performed in advance of an arriving job, and consists of two parts. During the first part of the setup, the job should not be present in the machine, while the second part of setup can be done in the presence or absence of the job. A heuristic algorithm is proposed, and its worst-case performance ratio of 4/3 is established. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule isNP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore{Gomory traveling salesman problem and solve it in polynomial time. c 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304{328, 2000 <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> Abstract This paper presents two mixed-integer linear programming (MILP) models (referred to as WST and SGST in the paper) for a family of four different M-machine, N -job flowshop sequencing problems. Each model may be used to solve the regular, no intermediate queues (NIQ), sequence-dependent setup times (SDST), and SDST/NIQ flowshop problems. The optimal job sequence, based on minimizing makespan, is achieved by a positional assignment approach in the WST model, and by pairs of disjunctive (either–or) constraints in the SGST model. A 12-cell experimental design was used to compare the solution times of the two models for each of the four flowshop problems. The WST model used significantly less computer time than the SGST model for all problem sizes in the regular, NIQ, and SDST flowshop problems. Both models were competitive in the SDST/NIQ flowshop for N ⩽7, but the WST model proved significantly better for N ⩾8. <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> We address the two-machine no-wait flowshop scheduling problem to minimize maximum lateness where setup and removal times are treated as separate from processing time. We obtain optimal solutions for special cases. Moreover, we propose a branch-and-bound algorithm for the generic case. We conduct extensive experimentations to evaluate the performance of the proposed branch-and-bound algorithm. The computational analysis shows that the branch-and-bound algorithm is quite efficient, especially when the setup and removal times are not too large compared to the processing times. Moreover, in the absence of removal times, the dominance property proposed by Dileepan appears to perform very well. <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> Ant colony optimization (ACO) is a meta-heuristic proposed to derive approximate solutions for computationally hard problems by emulating the natural behaviors of ants. In the literature, several successful applications have been reported for graph-based optimization problems, such as vehicle routing problems and traveling salesman problems. In this paper, we propose an application of the ACO to a two-machine flowshop scheduling problem. In the flowshop, no intermediate storage is available between two machines and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time. We first present a transformation of the scheduling problem into a graph-based model. An ACO algorithm is then developed with several specific features incorporated. A series of computational experiments is conducted by comparing our algorithm with previous heuristic algorithms. Numerical results evince that the ACO algorithm exhibits impressive performances with small error ratios. The results in the meantime demonstrate the success of ACO's applications to the scheduling problem of interest. <s> BIB006 </s> A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> This paper addresses the m-machine no-wait flowshop problem where the set-up time of a job is separated from its processing time. The performance measures considered are the total flowtime and makespan. The scheduling problem for makespan reduces to the travelling salesman problem (TSP), and the scheduling problem for total flowtime reduces to the time-dependent travelling salesman problem (TDTSP). Non-polynomial time solution methods are presented, along with a polynomial heuristic. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> Abstract Job scheduling for a two-machine flowshop where wait time between the first and the second machine is not permitted is studied in this paper. Aldowaisan and Allahverdi (J. Oper. Res. Soc. 53(9) (2002) 1004) considered this problem with minimizing total flowtime as the scheduling criterion and presented some necessary conditions for optimality. In this note their results have been modified for the scheduling criterion of minimizing maximum lateness. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> Consider the two-machine no-wait flowshop problem where the setup and removal times of a job at each machine are separated from the processing time. The scheduling objective is to minimize the sum of the total flowtime. Two optimization properties are first developed. In view of the NP-hard of this problem, optimal solutions seem unnecessary especially when the number of jobs is large. Then, combined the developed optimization properties with the greedy search a heuristic algorithm is developed. Computational experience demonstrates the effectiveness of the heuristic algorithm in finding near optimal schedules. <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> No-wait flow shop <s> This article deals with the no-wait flowshop problem with sequence dependent set-ups and ready times solved by an evolutionary approach. The hybrid genetic algorithm presented here addresses a new hierarchically organized complete ternary tree to represent the population that put together with a recombination plan resembles a parallel processing scheme for solving combinatorial optimization problems. Embedded in the hybrid approach, a novel recursive local search scheme, recursive arc insertion (RAI), is also proposed. The effectiveness of the local search phase is crucial given that it is responsible for about 90% of the total processing time of the algorithm. Instances with known optimal solution are used to test the new algorithm and compare it to a previously proposed heuristic approach. <s> BIB010
A no-wait flow shop problem occurs when the operations of the same job have to be processed contiguously from start to end without interruptions either on or between machines. Allahverdi and Aldowaisan (2000) considered the F 3=ST si ; no-wait= P C j problem. They found optimal solutions for problems where the setup and processing times satisfy certain conditions, and established a dominance relation. Furthermore, they presented five heuristics and evaluated the performance of these heuristics through computational experiments. The computational experiments revealed that one of the heuristics has an average error less than 0.01% for up to 18 jobs. The performance of the heuristics was compared with one another for larger number of jobs, up to 100. Aldowaisan and  proposed several heuristics and tested their effectiveness through extensive computational experiments for the F 3=ST si ; R si ; no-wait= P C j problem. They also obtained a dominance relation and presented a lower bound for the problem. BIB006 presented an Ant Colony Optimization algorithm for the F 2=ST si ; no-wait= P C j problem, and showed that their algorithm outperforms earlier heuristics. BIB007 presented non-polynomial time solution methods and a polynomial-time heuristic for the problem Fm=ST si ; no-wait= P f j . They also considered the C max criterion. Since all the jobs are assumed to be ready at time zero, the two criteria of P f j and P C j are equivalent. Ruiz and Allahverdi (in press-a) presented a dominance relation for the F 4=ST si ; no-wait= P C j , problem and proposed an iterated local search method for the Fm=ST si ; no-wait= P C j problem. Ruiz and Allahverdi (in press-a) compared the heuristics of BIB006 , BIB007 and Allahverdi and Aldowaisan (2000) , and showed that one of the heuristics of Allahverdi and Aldowaisan (2000) significantly outperforms the others. Ruiz and Allahverdi (in press-a) showed that their iterated local search method outperforms the best heuristic of Allahverdi and Aldowaisan (2000) . BIB008 obtained some dominance relations for the F2/ST si , no-wait/L max problem. BIB005 considered the same problem but treating the removal times as separated from the processing times, i.e., F2/ST si ,R si , no-wait/L max . They showed that certain sequences are optimal if certain conditions hold, and proposed a branchand-bound algorithm that can solve problems with up to 18 jobs. Their computational analysis showed that the branch-and-bound algorithm performs better when the setup and removal times are not too large in comparison with the processing times. Ruiz and Allahverdi (in press-b) proposed several heuristics and four new effective and efficient genetic algorithms for the Fm/ST si no-wait/L max problem. They also proposed a dominance relation for the case of three machines. BIB002 studied the F2/ST si , no-wait/ C max problem, where the setup time on the second machine consists of two parts. During the first part of the setup, the job must not be present at the machine, while the second part of the setup can be performed in the presence or absence of the job. They proposed a heuristic algorithm and established its worst-case performance ratio to be 4/3. BIB009 derived two dominance relations for the F 2=ST si ; R si ; no-wait= P f j problem, where all the jobs are ready at time zero. They also proposed a greedy search heuristic algorithm for the problem. Allahverdi and Aldowaisan (2001) stated that the two-machine problem with the additive sequence-dependent setup times is equivalent to the problem addressed by BIB009 . There is no information on comparison of the heuristic proposed by BIB009 and the heuristics presented by Allahverdi and Aldowaisan (2001) . BIB003 addressed the F2, S/ST si , nowait/C max problem for the case where the setup operation is performed by a single server. They reduced the problem to the Gilmore-Gomory traveling salesman problem and solved it in polynomial time. Allahverdi and Aldowaisan (2001) considered the F 2=ST sd ; no-wait= P C j problem. They showed that certain sequences are optimal if certain conditions hold. Moreover, they developed a dominance relation and presented several heuristics with the computational complexities of O(n 2 ) and O(n 3 ). The heuristics consist of two phases; in the first phase a starting sequence is developed, and in the second a repeated insertion technique is applied to get a solution. Computational experiments demonstrated that the concept of repeated insertion application is quite useful for any starting sequence, and that the solutions for all the starting sequences converge to about the same value after a few number of iterations. BIB001 addressed the problem of Fm/ST sd , no-wait, r j /C max . They showed that the problem is equivalent to the asymmetric traveling salesman problem with additional visiting time constraints. They presented lower bounds, an integer programming formulation, and two heuristics for the problem. They also evaluated the performance of the lower bounds and heuristics by using randomly generated data. BIB010 proposed a hybrid genetic algorithm for the same problem. They showed that their hybrid genetic algorithm performs better than the heuristics of BIB001 for a vast majority of randomly generated problem instances. BIB004 proposed two mixed-integer linear programming models for the Fm/ST sd , no-wait/C max problem.