A survey of scheduling problems with setup times or costs <s> Flexible flow shop <s> Abstract This paper explores scheduling flexible flow lines with sequence-dependent setup times. Three major types of heuristics are explored. Insertion heuristics (based on insertion heuristics for the traveling salesman problem) attempt to simultaneously equalize workload on all processors at a stage, and minimize total or single-stage flowtimes. Johnson's algorithm for two-stage flow shops and its heuristic extensions to m-machine flow shops are modified for parallel processors and the flexible flow-line environment. A set of naive greedy heuristics is investigated for comparison purposes. The performance of the heuristics is compared on a set of test problems. Results indicate the range of conditions under which each method performs well. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Flexible flow shop <s> Abstract This paper examines scheduling in flexible flow lines with sequence-dependent setup times to minimize makespan. This type of manufacturing environment is found in industries such as printed circuit board and automobile manufacture. An integer program that incorporates these aspects of the problem is formulated and discussed. Because of the difficulty in solving the IP directly, several heuristics are developed, based on greedy methods, flow line methods, the Insertion Heuristic for the Traveling Salesman Problem and the Random Keys Genetic Algorithm. Problem data is generated in order to evaluate the heuristics. The characteristics are chosen to reflect those used by previous researchers. A lower bound has been created in order to evaluate the heuristics, and is itself evaluated. An application of the Random Keys Genetic Algorithm is found to be very effective for the problems examined. Conclusions are then drawn and areas for future research are identified. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Flexible flow shop <s> Much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper deals with the hybrid flow shop scheduling problems in which there are sequence dependent setup times, commonly known as the SDST hybrid flow shops. This type of production system is found in industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacture. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become ineffective. An immune algorithm (IA) can be used to tackle complex problems and produce a reasonable manufacturing schedule within an acceptable time. This paper describes an immune algorithm approach to the scheduling of a SDST hybrid flow shop. An overview of the hybrid flow shops and the basic notions of an IA are first presented. Subsequently, the details of an IA approach are described and implemented. The results obtained are compared with those computed by Random Key Genetic Algorithm (RKGA) presented previously. From the results, it was established that IA outperformed RKGA. <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Flexible flow shop <s> After 50 years of research in the field of flowshop scheduling problems the scientific community still observes a noticeable gap between the theory and the practice of scheduling. In this paper we aim to provide a metaheuristic, in the form of a genetic algorithm, to a complex generalized flowshop scheduling problem that results from the addition of unrelated parallel machines at each stage, sequence dependent setup times and machine eligibility. Such a problem is common in the production of textiles and ceramic tiles. The proposed algorithm incorporates new characteristics and four new crossover operators. We show an extensive calibration of the different parameters and operators by means of experimental designs. To evaluate the proposed algorithm we present several adaptations of other well-known and recent metaheuristics to the problem and conduct several experiments with a set of 1320 random instances as well as with real data taken from companies of the ceramic tile manufacturing sector. The results indicate that the proposed algorithm is more effective than all other adaptations. <s> BIB004
Liu and Chang (2000) addressed the problem of FFm/ST sd , SC sd ,r j with the objective of minimizing the sum of setup times and costs.They first formulated the problem as a separable integer programming problem. Then Lagrangian relaxation was utilized, and finally a search heuristic was proposed. BIB001 studied the FFm/ST sd / C max problem with missing operations, where the machine routes for some jobs contain less than m machines, i.e., all the jobs need not visit all the stages. They explored three types of heuristics for the problem, namely, insertion heuristics, Johnson's based heuristics, and greedy heuristics. They identified the range of conditions under which each method performs well. BIB002 compared four heuristics, including the random keys genetic algorithm, for the problem. They developed lower bounds and utilized these bounds in the evaluation of the proposed heuristics. The computational experiments showed that the random keys genetic algorithm performs best. BIB003 proposed an immune algorithm, and showed that this algorithm outperforms the random keys genetic algorithm of BIB002 .  developed three tabu searchbased algorithms for the same problem. In order to aid the search algorithms with a better initial solution, they considered three different initial solution finding mechanisms. A detailed statistical experiment based on the split-plot design was performed to analyze both makespan and computation time as two separate response variables. BIB004 also studied the FFm/ST sd /C max problem, but in a more complex environment, where the machines in each stage are unrelated and some machines are not eligible to perform some jobs. Ceramic tiles are manufactured in such environments. BIB004 proposed a genetic algorithm, where they conducted an extensive calibration of the different parameters and operators by means of experimental designs.  addressed the FFm=ST sd = P w j f j problem, where some jobs may have missing operations on some machines. They proposed a heuristic procedure to derive a non-per-mutation schedule from a given permutation sequence. They tested the performance of the proposed heuristics and showed that it performs well.  considered the FFm=ST sd =kC max þ ð1 À kÞ P U j problem for the case of unrelated parallel machines, where 0 6 k 6 1. They adapted the well known constructive heuristics and iterative heuristics (genetic algorithm and simulated annealing) for the pure flow shop problems. The computational results indicated that among the constructive heuristics, a job insertion based heuristic outperforms the other constructive heuristics, while the genetic algorithm outperforms the simulated annealing among the iterative heuristics. Ruiz et al. (in press ) presented a mathematical model and some heuristics for the FFm/ST sd , prec/ C max problem, where several realistic characteristics are jointly considered such as release dates for machines, unrelated parallel machines in each stage, machine eligibility, possibility of the setup times to be both anticipatory and non-anticipatory, and time lags. The same problem is being studied in where a set of different genetic algorithms are used for obtaining near optimal solutions for small instances and good solutions for larger ones where the previously proposed mathematical model was shown inefficient.