A survey of scheduling problems with setup times or costs <s> Flexible (hybrid) flow shop <s> This paper studies the two-stage no-wait hybrid flowshop scheduling problem where one of the two stages consists of several identical parallel machines and the setup and removal times of each job at each stage are separated from the processing time. In view of the NP-complete of this problem, heuristic algorithms regarding sequencing and assigning of jobs to each stage as independent procedure are proposed. Two theorems are also proposed for sequencing job procedure. Computational experience demonstrates the effectiveness of the heuristic algorithm including the proposed theorems in finding a near optimal schedule. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Flexible (hybrid) flow shop <s> This article addresses a multi-stage flow shop scheduling problem with unrelated parallel machines. Some practical processing restrictions such as independent setup and dependent removal times are taken into account as well. The objective is to minimize total flow time in the system. A simulated annealing (SA)-based heuristic is proposed to solve the addressed problem in a reasonable running time. The heuristic begins on a well-designed initial solution generator; then a simulated annealing procedure is applied for further improvement of the solution. To assure the quality and efficiency of the solution for the proposed SA-based heuristic, certain mechanisms are developed and introduced into the heuristic. The computational experimental results show that the proposed SA-based heuristic performs well with respect to accuracy and efficiency of solution. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Flexible (hybrid) flow shop <s> Abstract Flexible flow shops are becoming increasingly common in industry practice due to higher workloads imposed by jobs. As a result, one or more stages in a flexible flow shop will have two or more units of the same machine type. The group scheduling problem, comprised of two levels of scheduling, is investigated in this paper to minimize the makespan in a flexible flow shop. At the first level, a sequence of jobs in each group is determined, while at the second level a sequence of groups themselves is determined. A statistical model based on split-plot design is developed to conduct the experiments to compare the performance of three different heuristic solution algorithms. These comparisons are based on either single setup or multiple setups on machines for processing jobs in the same group. The single setup assumes that only one machine in a stage can be setup for a group, while the multiple setups assumes that more than one machine in a stage can be setup for a group. Three different problem structures representing sizes ranging from small, medium to large have been considered as the main factor along with flexibility introduced in the shop, setup-to-run time ratio, and solution algorithms as sub plot factors, thus resulting in a 34 factorial split-plot design. The higher the number of stages and the number of parallel machines in each stage, higher is the flexibility introduced in the shop. The results show that for small and medium size problems whether or not a computationally more demanding algorithm is employed to solve the level 1 or level 2 problem does not have any bearing on the makespan evaluated. This situation changes dramatically when large size problems are attempted, as a single-setup algorithm which combines the use of single- and multiple-pass heuristic for the level 2 and level 1 problems, respectively, outperforms another single-setup algorithm with the order of use reversed at all levels of flexibility. Test results also show that a multiple-setup algorithm is no worse than the single-setup algorithms and is sometimes much better. Hence, it is recommended for solving group scheduling problems in flexible flow shops. <s> BIB003
A flexible flow shop is an extension of a regular flow shop, where in each stage there may be more than one machine in parallel as a result of the need to increase the capacity in that stage. Each job still needs to be processed first in stage 1, then in stage 2, and so on. In some cases, not all the jobs need to go through all the stages but still all the jobs have to follow the same machine route. This problem is known as the flexible flow line problem. It can be assumed that the job has zero processing time in the skipped stage. Therefore, we will refer to both problems as flexible flow shops. Botta-Genoulaz (2000) studied the FFm/ST si , R si , prec/L max problem with minimum time lags (between two successive operations) such as transportation time. Botta-Genoulaz proposed six different heuristics and evaluated their performances. BIB002 addressed the FFm=ST si ; R sd = P f j problem, where in each stage there are several unrelated parallel machines and the jobs are ready at time zero. He proposed a heuristic to generate an initial solution, and a simulated annealing algorithm to improve the initial solution. The efficiency of the hybrid approach was tested by computational experiments. BIB001 addressed the FF2/ST si , R si , no-wait/C max problem, where there is only one machine in the first stage, while there are m parallel machines in the second stage. They developed dominance relations and proposed two heuristics. Allaoui and Artiba (2004) addressed the FFm/ ST si problem with respect to the criteria of C max , T max , P T j , P U j and P C j with machine unavailability intervals (due to breakdowns preventive maintenance), where the transportation times between the stages are explicitly considered. Two types of strategies are possible to follow when a job is interrupted as a result of machine unavailability. If the job continues processing after the machine becomes available, the strategy is called preemptresume, while it is called preempt-restart if the job has to restart processing from the beginning (all prior processing is wasted). Allaoui and Artiba (2004) considered both preempt-resume and preempt-restart strategies. They integrated simulation and optimization to solve the problem. They showed through computational experiments that the performance of their proposed heuristic with respect to the considered criteria is affected by the percentage of repair time. BIB003 investigated constructive heuristics for a generalization of the problem FFm/ ST si /C max , where the jobs are partitioned into several families and jobs of the same family assigned on the same machine should be processed jointly. Machine dependent and sequence (of families) independent setup times are given.  considered the hybrid flow shop scheduling problem to minimize makespan for the case that a job can be processed by more than one machine simultaneously, known as multiprocessor jobs. They presented several algorithms and two metaheuristics based on tabu search and simulated annealing.