A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> In this paper, we propose different heuristic algorithms for flow shop scheduling problems, where the jobs are partitioned into groups or families. Jobs of the same group can be processed together in a batch but the maximal number of jobs in a batch is limited. A setup is necessary before starting the processing of a batch, where the setup time depends on the group of the jobs. In this paper, we consider the case when the processing time of a batch is given by the maximum of the processing times of the operations contained in the batch. As objective function we consider the makespan as well as the weighted sum of completion times of the jobs. For these problems, we propose and compare various constructive and iterative algorithms. We derive suitable neighbourhood structures for such problems with batch setup times and describe iterative algorithms that are based on different types of local search algorithms. Except for standard metaheuristics, we also apply multilevel procedures which use different neighbourhoods within the search. The algorithms developed have been tested in detail on a large collection of problems with up to 120 jobs. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> Abstract In this paper, we examine the scheduling of jobs, each of which comprises a standard and a specific component, on a single machine. A set-up time is required before each batch of standard components is processed. A job is completed when both its standard and specific components have been processed and are available. Standard components only become available when the batch to which they belong is completed, whereas specific components are available on completion of their processing. We present results for two well-known due-date related criteria. In particular, an O( n 2 ) dynamic programming algorithm is derived for the problem of minimising the maximum lateness. For minimising the number of late jobs, we show that the problem is NP-hard and give a dynamic programming algorithm that requires pseudo-polynomial time. Finally, we show that a variant of the number of late jobs problem, in which there is a common processing time for the standard components, is solvable in O (n 4 log n) time. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> Abstract This paper considers a two-machine flowshop group scheduling problem. The jobs are classified into groups and the jobs in the same group must be processed in succession. Each group requires a set up time and removal time on both machines. A transportation time is required for moving the jobs from machine 1 to machine 2. The objective is to minimize the maximum completion time (makespan). A polynomial time algorithm is proposed to solve the problem. This generalizes the algorithms proposed by Baker and others. Scope and purpose Recently, an important class of scheduling problem is characterized by a group scheduling constraint where the jobs are classified into groups by the same operation requirements or characters. Each group requires a setup time and removal time on both machines. That is, each machine needs a time to set up or to remove the tools, jigs and fixtures when the group starts processing or completes processing. A transportation time is required to move the jobs between the machines. The objective is to find a sequence of groups and jobs in each group such that the maximum completion time (makespan) is minimized. Baker provided an optimal algorithm for this problem in the case of two-machine flowshop group scheduling without considering the removal and transportation times. But, in some manufacturing environments, it is required to consider the group removal time and job transportation time. The main contribution of this paper is to develop a polynomial time algorithm, which generalizes the algorithms proposed by Baker and others. <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part-types are to be produced in a flexible manufacturing cell organized into a two-stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP-hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 128–144, 2000 <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> This paper presents a job scheduling model of M identical machines in parallel. The model assumes that a set-up time is incurred when a machine changes from processing one type of parts to a different type of parts. And the scheduling objective is to minimize the sum of total flow time. We establish a heuristic and a tight lower bound (LB) on the optimal total flow time. The solution is analyzed by computational study. The comparisons of LB with heuristic and optimal solutions of small instances show that the solution quality of our heuristic is acceptable, and the heuristic has potential to solve larger practical problems. <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> Abstract We address the problem of scheduling jobs with family setup times on identical parallel machines to minimize total weighted flowtime. We present two dynamic programming algorithms — a backward algorithm and a forward algorithm — and we identify characteristics of problems where each algorithm is best suited. We also derive two properties that improve the computational efficiency of the algorithms. Scope and purpose While most production schedulers must balance conflicting goals of high system efficiency and timely completion of individual jobs, consideration of this conflict is underdeveloped in the scheduling literature. This paper examines a model that incorporates a fundamental cause of the efficiency/timeliness conflict in practice. We propose solution methodologies and properties of an optimal solution for the purpose of exposing insights that may ultimately be useful in research on more complex models. <s> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> Abstract We consider a scheduling problem where a set of jobs are simultaneously available for processing in a no-wait two-machine flowshop. The objective is to minimize the makespan, i.e. the maximum completion time of the jobs. The operations of all jobs are processed on both machines in batches. A constant setup time is incurred whenever a batch is formed on the machines. The processing time of a batch is defined as the setup time plus the sum of all processing times of the jobs it contains. The completion time of a job is defined as the time at which the batch containing it is completely processed on machine two. The no-wait scheduling problem in the two-machine flowshop without batching is known as polynomially solvable. We show that several restricted versions of the problem under study in this paper are strongly NP -hard, which imply that the general problem is also strongly NP -hard. We then establish some interesting properties and exploit them to design solution methods for two special cases. Scope and purpose In this paper, we consider scheduling a set of jobs in a two-machine no-wait flowshop, which is a typical manufacturing setup for steel and plastic production. The jobs are sequentially processed on the machines in batches. A constant setup time is incurred whenever a batch is formed on any of the machines. Our goal is to finish all jobs in the earliest possible time. We first give NP -hardness proofs for three special cases. These results suggest that it is very unlikely to devise an efficient method to find an optimal schedule for the problem under study. We also design solution procedures for two further restricted cases, in which the jobs share some specific characteristics. This paper initiates research into scheduling with batching in the no-wait flowshop environment. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these asconsistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> Abstract The problem of makespan minimization in a flow shop with two-machines when the input buffer of the second machine can only host a limited number c of parts is known to be NP-hard for any c >0 and c ⩽ n , where n is the number of jobs. In this paper we analyze this problem in the context of batch scheduling, i.e. when identical parts must be processed consecutively. In particular we study the case in which each batch requires sequence independent setup times and removal times. We then show that, if the size of the i th batch is larger than a value b i ∗ , then the makespan minimization problem can be formulated as a special case of TSP and solved in polynomial time. The cost structure of this TSP can be reduced to the one defined for the two-machine no-wait flow shop. Hence, we give a closed form expression for b i ∗ . Then, we prove that when the same algorithm is applied to batch sizes smaller than b i ∗ , the error goes to zero as the batch sizes approach the values b i ∗ . <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> This paper presents a scheduling problem for unrelated parallel machines with sequence-dependent setup times, using simulated annealing (SA). The problem accounts for allotting work parts of L jobs into M parallel unrelated machines, where a job refers to a lot composed of N items. Some jobs may have different items while every item within each job has an identical processing time with a common due date. Each machine has its own processing times according to the characteristics of the machine as well as job types. Setup times are machine independent but job sequence dependent. SA, a meta-heuristic, is employed in this study to determine a scheduling policy so as to minimize total tardiness. The suggested SA method utilizes six job or item rearranging techniques to generate neighborhood solutions. The experimental analysis shows that the proposed SA method significantly outperforms a neighborhood search method in terms of total tardiness. <s> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> This paper proposes an efficient heuristic to minimise the total weighted tardiness of a set of tasks with known processing times, due dates, weights and family types for parallel machines. A three-phase heuristic is presented to minimise total weighted tardiness. In the first phase, jobs are listed by the earliest due date and then divided into small job-sets according to a decision parameter. In the second phase, jobs are grouped by the due date within applicable families using apparent tardiness cost with set-up (ATCS), and the sequence of jobs within families is improved through the use of the tabu search method. In the third phase, jobs are allocated to machines using a threshold value and a look-ahead parameter. The comprehensive simulation results show that the proposed heuristic performs better than the ATCS and rolling horizon procedure at a significantly reduced total weighted tardiness. <s> BIB011 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> Lot splitting is a technique for accelerating the flow of work by splitting job lots into sublots, In this paper we investigate the lot splitting scheduling problem in a two-machine flow-shop environment with detached setups and with batch availability. The performance measure considered is the average flow-time which is indicative of the increasingly important manufacturing lead-time. Our contribution is both theoretic and practical for the case of general (not necessarily equal) sublots. We identify properties of the optimal solution and develop a solution procedure to solve the problem. We then present a computational study which indicates that our solution technique is very efficient. <s> BIB012 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> This paper considers a fabrication scheduling problem to minimize the makespan in a two-machine flowshop. Each job has a unique component and a common component to be processed on the first machine. On machine 1, the common components of the jobs are grouped into batches for processing with a setup cost incurred whenever a batch is formed. A job is ready for its assembly operation on the second machine if both its unique and common components are finished on machine 1. The problems with batch availability and item availability are known as NP-hard. In this paper, we give proofs for the strong NP-hardness of the two problems. The results suggest that it is very unlikely to develop polynomial- or pseudo-polynomial-time algorithm for finding exact solutions for the two problems. <s> BIB013 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> We describe and evaluate several branch-and-bound algorithms for an identical parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted flowtime. The algorithms differ by choice of lower bound method. Computational results suggest conditions favourable to a particular algorithm as well as the range of problem sizes that can be optimally solved in reasonable CPU time. <s> BIB014 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 823–840, 2003. <s> BIB015 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> A model for scheduling grouped jobs on identical parallel machines is addressed in this paper. The model assumes that a set-up time is incurred when a machine changes from processing one type of component to a different type of component, and the objective is to minimize the total earliness-tardiness penalties. In this paper, the algorithm of soft computing, which is a fuzzy logic embedded Genetic Algorithm is developed to solve the problem. The efficiency of this approach is tested on several groups of random problems and shows that the soft computing algorithm has potential for practical applications in larger scale production systems. <s> BIB016 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> A model of scheduling grouped jobs on identical parallel machines is discussed. The model assumes that a set-up time is incurred when a machine changes from processing one type of parts to a different type of parts, and the objective is to minimize the total flow time. The algorithm of fuzzy logic embedded genetic algorithm is developed to solve the problem. The efficiency of this approach is tested on several groups of random problems and shows that soft computing algorithm has potential for practical applications in larger scale production systems. <s> BIB017 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> Abstract There is a set of jobs available to process in batches on a set of identical parallel machines. A sequence-independent setup time is incurred whenever a batch is formed on any machine. The jobs in the same batch are continuously processed after the setup. The processing length of a batch is the sum of the setup time and the processing times of the jobs it contains. Under the batch availability constraint, the completion time of a job is defined as the time when the batch it belongs to is totally completed. With each job, a due date is specified for its completion. In this paper, we first consider the problem to schedule as well as group the jobs so that the maximum lateness is minimized. The second problem is to minimize the number of tardy jobs. We first design dynamic programming algorithms for finding optimal solutions to the two problems. Then, we design several heuristics and conduct computational experiments to study their relative performance. <s> BIB018 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> Abstract This research addresses lead-time reduction and makespan minimization for cut and sew operations of upholstered furniture manufacturing through efficient scheduling. Jobs are grouped based on different characteristics at each operation of this two stage flow line. There are identical parallel machines at each stage and jobs proceed individually from the 1st stage to the 2nd. A heuristic for the case of multiple setups per group at the 2nd stage is developed, compared to a single setup per group at each stage, and integrated into a genetic algorithm. Results demonstrate that the heuristic effectively adds minimal setups to a single setup schedule while significantly improving schedule makespan. <s> BIB019 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> In many practical situations of production scheduling, it is either necessary or recommended to group a large number of jobs into a relatively small number of batches. A decision needs to be made regarding both the batching (i.e., determining the number and the size of the batches) and the sequencing (of batches and of jobs within batches). A setup cost is incurred whenever a batch begins processing on a given machine. This paper focuses on batch scheduling of identical processing-time jobs, and machine- and sequence-independent setup times on an m-machine flow-shop. The objective is to find an allocation to batches and their schedule in order to minimize flow-time. We introduce a surprising and nonintuitive solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004 <s> BIB020 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> In this paper, the mean flowtime and the makespan objectives are simultaneously investigated in a single product, m-machine, flowshop system. For this purpose, an efficiency frontier approach is applied and an optimal algorithm for generating all efficient solutions is developed. A comprehensive computational experiment is performed for analyzing the tradeoff between the two objectives and evaluating the proposed algorithm performance. The most-balanced-solution, MinMax, is defined and recommended as a desirable alternative for either the flowtime or the makespan optimal solutions. Results show that when the system is optimized for either the mean flowtime or the makespan, a significant loss in the nonoptimized objective value is observed. On the other hand, adopting the MinMax solution obtains a close to optimal solution in both objectives. <s> BIB021 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> The problem of batching and scheduling n identical jobs of F, F ≥ 2, part types in a shop made up of F+1 machines is studied. The processing of each job comprises two stages. The first stage is undertaken on the machine common to all jobs and the second stage is undertaken on the machine specific to a particular part type. Setup times are necessary at the first stage to switch processing from a job of one part type to a job of another part type. Jobs of the same part type processed contiguously at the first stage form a batch. The objective is to find a batch schedule minimizing makespan. We show that this problem is equivalent to a special case of a single machine family scheduling problem to minimize maximum lateness and therefore it can be solved in O(n F ) time by a known algorithm. Furthermore, for the case where F = 2, we present an iterative exact algorithm with O(k 0log L) running time, where k 0 is the maximum number of batches in a schedule created in any iteration of the algorithm and L is the ... <s> BIB022 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> The two-stage assembly scheduling problem is a model for production processes that involve the assembly of final or intermediate products from basic components. In our model, there are m machines at the first stage that work in parallel, and each produces a component of a job. When all components of a job are ready, an assembly machine at the second stage completes the job by assembling the components. We study problems with the objective of minimizing the makespan, under two different types of batching that occur in some manufacturing environments. For one type, the time to process a batch on a machine is equal to the maximum of the processing times of its operations. For the other type, the batch processing time is defined as the sum of the processing times of its operations, and a setup time is required on a machine before each batch. For both models, we assume a batch availability policy, i.e., the completion times of the operations in a batch are defined to be equal to the batch completion time. We provide a fairly comprehensive complexity classification of the problems under the first type of batching, and we present a heuristic and its worst-case analysis under the second type of batching. <s> BIB023 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> We consider the scheduling of N jobs divided into G families for processing on M identical parallel machines. No set-up is necessary between jobs belonging to the same family. A set-up must be scheduled when switching from the processing of family i jobs to those of another family j, i ≠ j, the duration of this set-up being the sequence-independent set-up time sj for family j. We propose heuristics for this problem and computationally evaluate the performance of the heuristics relative to lower bounds and solutions obtained using an exact algorithm. <s> BIB024 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> This paper studies the two-machine flowshop scheduling problem with job class setups to minimize the total flowtime. The jobs are classified into classes, and a setup is required on a machine if it switches processing of jobs from one class to another class, but no setup is required if the jobs are from the same class. For some special cases, we derive a number of properties of the optimal solution, based on which we design heuristics and branch-and-bound algorithms to solve these problems. Computational results show that these algorithms are effective in yielding near-optimal or optimal solutions to the tested problems. <s> BIB025 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution. <s> BIB026 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> This research deals with scheduling jobs on unrelated parallel machines with auxiliary equipment constraints. Each job has a due date and requires a single operation. A setup for dies is incurred if there is a switch from processing one type of job to another type. For a die type, the number of dies is limited. Due to the attributes of the machines and the fitness of dies to each, the processing time for a job depends on the machine on which the job is processed, each job being restricted to processing on certain machines. In this paper, an effective heuristic based on threshold-accepting methods, tabu lists, and improvement procedures is proposed to minimize total tardiness. An extensive experiment is conducted to evaluate the computational characteristics of the proposed heuristic. Computational experiences demonstrate that the proposed heuristic is capable of obtaining optimal solutions for small-sized problems, and significantly outperforms an ATCS procedure and a simulated annealing method for problems in larger sizes. <s> BIB027 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> This paper presents a new approach for transforming MRP orders, planned periodically, e.g. on a weekly base, into a detailed schedule of jobs. In this model for a parallel machine environment, the jobs are partitioned into families and a family specific set-up time is required at the start of each period and of each batch, where a batch is a maximal set of jobs in the same family, that are processed consecutively. An integer program is formulated for both the problem of minimising the number of overloaded periods and the problem of minimising the total overtime. These programs generate benchmark results for the heuristic approach. A heuristic model is developed that constructs a schedule in which overloaded periods are relieved and set-up time is saved. In this approach, the job sequence is constructed by repeatedly solving a knapsack problem for each machine. The weights used in this knapsack problem relate to the preferred priorities of the jobs not yet scheduled and determine the quality of the final sequence. The different features of the heuristic model are compared using a large set of test problems. The results show that the quality of the final schedule depends on an appropriate choice of the weights. <s> BIB028 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> This paper considers the problem of scheduling part families and jobs within each part family in a flowline manufacturing cell with independent family setup times where parts (jobs) in each family are processed together. The objective is to minimize total flow time. A branch-and-bound algorithm capable of solving moderate sized problems is developed. Several heuristic algorithms are proposed and empirically evaluated as to their effectiveness and efficiency in finding optimal permutation schedules. These results show that several heuristic algorithms generate solutions that are better than those generated by an existing genetic algorithm. <s> BIB029 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> This paper studies the two-machine flowshop scheduling problem with class setups in a no-wait processing environment to minimize the maximum lateness. The jobs are divided into job classes and a setup is required at the initial processing of a job or between the processing of jobs of different classes. In a no-wait environment, a job must be processed from start to finish without interruptions on a machine or between the machines. A batch is a maximal subset of consecutively processed jobs of the same class. Several properties concerning the beneficial merging of batches and some dominance rules that improve the objective function are derived. Since the problem is NP-hard, a heuristic is proposed and evaluated computationally. The numerical results demonstrate that the heuristic can produce near-optimal solutions quickly for realistic-sized problems. <s> BIB030 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-independent setup times <s> Abstract This paper considers a two-machine multi-family scheduling problem with reentrant production flows. The problem consists of two machines, M1 and M2, and each job has the processing route (M1, M2, M1, M2). There are identical jobs in the same family and the jobs in the same family are processed in succession. Each machine needs a setup time before the first job in a family is processed. The objective is to minimize the maximum completion time. Examples of such a problem occur in the bridge construction, semiconductor industry and job processing on numerical controlled machines, where they usually require that the jobs are reprocessed once and there are identical jobs in the same family. This problem is shown to be NP-hard. A branch-and-bound algorithm is proposed, and computational experiments are provided. <s> BIB031
Yi and Wang (2001a) proposed a tabu search algorithm, while BIB005 presented a lower bound for the P =ST si;b = P f j problem with the assumption that the jobs are ready at time zero. BIB017 proposed a fuzzy logic embedded genetic algorithm for the same problem. BIB006 and BIB014 addressed the same problem with a weighted objective function, i.e., P =ST si;b = P w j f j , or equivalently P =ST si;b = P w j C j . Two dynamic programming algorithms (a backward and a forward) were proposed by BIB006 , where they also identified the characteristics of the problems for which each algorithm is suitable. When the number of machines and families are fixed, the backward dynamic algorithm is polynomial in the sum of the weights while the forward dynamic algorithm is polynomial in the sum of processing and setup times. BIB014 presented several branch-and-bound algorithms for the problem and computationally evaluated the performance of each algorithm. They concluded that the algorithms can quickly generate optimal solutions for problems with up to 15 to 25 jobs, depending on the number of machines. BIB015 proposed column generation based branch-and-bound algorithms for the same problem, where they obtained optimal solutions for problems up to 40 jobs, 4 machines and 6 families.  presented another branch-and-bound algorithm for the same problem and they showed that their algorithm outperforms that of BIB014 . They solved problems with up to 25 jobs and 8 families using their branch-and-bound algorithm. BIB024 proposed several simple heuristics for the same problem. Clearly, the branch-and-bound algorithms of BIB015 , and of  remain to be compared. Also, the heuristics of BIB017 and of BIB024 remain to be compared for at least the same weight of all the jobs since BIB017 considered the case of non-weighted jobs. BIB015 proposed column generation based branch-and-bound algorithms for the P =ST si;b = P w j U j problem. They obtained optimal solutions for problems with up to 40 jobs, 6 families, and 4 machines. BIB027 addressed the R=ST si;b = P T j problem and proposed a heuristic based on threshold-accepting methods, tabu list, and improvement procedures. They showed by computational analysis that the heuristic significantly outperforms a simulated annealing heuristic. BIB016 considered the P =ST si;b = P w j E j þ P w j T j problem, where the jobs have a common due date. They proposed a fuzzy logic embedded genetic algorithm (called soft computing) to solve the problem. Gambosi and Nicosia (2000) proposed an on-line algorithm for the P/ST si,b /C max problem and derived an upper bound on its competitive ratio. They also derived a lower bound on the competitive ratio for any on-line algorithm. BIB028 proposed an integer programming formulation and several heuristics for the P/ST si,b , r j , d j problem for a number of performance measures including minimization of the number of setups. Cheng and Kovalyov (2000) studied a single family problem of scheduling jobs by their deadlines on unrelated parallel machines under the batch availability model. Each batch is preceded by a constant setup time. They suggested a dynamic programming algorithm and an approximation scheme with O(n 2m+1 /e m ) running time. The scheme delivers a schedule satisfying C j 6 (1+e)d j for all the jobs if a feasible (with respect to the due dates) schedule exists. The case of uniform machines and identical jobs was proved to be strongly NP-hard and solvable in O(m 2 n 2m+1 ) time. If the machines are identical and job processing times are all equal to the setup time, the problem can be solved in O(n log n) time. The single family problems P/ST si,b /L max and P =ST si;b = P U j with common batch setup time were studied by BIB018 under the batch availability model. Dynamic programming algorithms that are pseudopolynomial for a fixed number of machines were presented, as well as heuristics based on the smallest completion time first and smallest lateness first rules. BIB019 studied the problem P/ r j , ST si,b /C max with a common batch setup time motivated by planning of cut and sew operations in upholstered furniture manufacturing. They suggested a batch splitting and scheduling heuristic and integrated this heuristic into a genetic algorithm. Similar to BIB002 for a single machine problem, Yang (2004a) studied a parallel machine problem in which each job consists of two components: standard and specific to be processed in this order on the same machine. Standard components are processed in batches under the batch availability model. Each batch is preceded by a constant setup time. A job is completed when both of its components are completed. For P C j minimization, Yang proposed two constructive heuristics. BIB010 addressed the R=ST sd;b = P T j problem, where the jobs in the same family have the same due date. They proposed a simulated annealing algorithm that utilizes job rearranging techniques to generate neighborhood solutions. They indicated by computational analysis that the simulated annealing algorithm outperforms a neighborhood search method. BIB011 proposed a three-phase heuristic for the P =ST sd;b = P w j T j problem. Tabu search is used in the final phase of the algorithm. A comparison of the simulated annealing algorithm of BIB010 and the heuristic of BIB011 remains to be performed for at least the case with equal weights and identical machines since BIB011 considered the identical machines case. The P =ST sd;b ; r j = P T j problem was addressed by  for the case involving the so-called calendar constraints. They presented a simulated annealing heuristic by introducing several neighborhood mechanisms. By computational experiments they showed that their proposed neighborhood mechanisms produce better results in a shorter time compared with several greedy heuristics and a basic simulated annealing procedure. Since not many papers exist in this category, we will not separately analyze them under different shop environments. BIB025 derived a number of properties of the optimal solution for the F 2=ST si;b = P f j problem where jobs are ready at time zero. They also proposed a branch-and-bound algorithm and a heuristic to solve the problem. They showed that the branch-and-bound algorithm can solve problems with up to 30 jobs and 10 families. BIB029 presented a branchand-bound algorithm for the same problem with m machines and under the group technology assumption, i.e., Fm=ST si;b = P f i . They also proposed and evaluated several heuristics for the problem. BIB003 addressed the F2/ ST si,b , R si,b /C max problem under the group technology assumption, where a transportation time is required for moving the jobs from the first machine to the second machine. They proposed a polynomial-time algorithm to solve the problem for the case of permutation schedules. BIB007 investigated the single family problem F2/ST si,b , no-wait/C max with a common non-anticipatory batch setup time under the batch availability model. The problem was proved to be strongly NP-hard even if all the processing times on one of the machines are equal. A formula for the optimal batch size was given if all the operations of all the jobs have the same processing time. The problem is solvable in O(n 3 ) time if the job processing times are the same on each machine but different from one machine to the other machine. BIB030 addressed the F2/ ST si,b , no-wait/L max problem where they obtained some dominance relations, proposed a branchand-bound algorithm and a heuristic for the problem. They showed by computational experiments that the branch-and-bound algorithm can solve problems with up to 30 jobs and 10 families, and the heuristic can produce near optimal solutions (on average, the error is less than 1%) for the considered problems. The reentrant flow shop problem of F2/ST si,b / C max was shown to be NP-hard by BIB031 under the assumption of group technology and the assumption that each family consists of identical jobs. They presented some dominance relations and proposed a branch-and-bound algorithm. Huang and Li (1998) studied the FF2/ST si,b /C max problem under the group technology assumption, where the first stage consists of only one machine and the second stage consists of multiple uniform machines. They presented two heuristics to solve the problem and derived a model to determine the trade-offs between the costs and the speeds of the machines in the second stage. Several authors have studied a single family flow shop problem under the batch availability model with anticipatory or non-anticipatory machine dependent setup times. For C max minimization, suggested an O(n) time algorithm for the m-machine flow shop, equal setup times and equal job processing times. BIB004 considered the above problem under the assumptions that there are two machines, setups are non-anticipatory and equal, and schedules are permutation ones with consistent batches. They proved that this problem is NP-hard in the strong sense, derived several properties of an optimal schedule, and developed O(n), O(n 2 ) and O(n 3 ) time algorithms for the cases where (1) all the processing times are the same, (2) the processing times on one of the machines are the same, and (3) the processing times can be oppositely ordered on machines 1 and 2. They also suggested several constructive heuristics for the general case of their problem. BIB008 studied the two-machine problem under the assumption that the setups are anticipatory. They proved that when batches are consistent in an optimal schedule, the problem is strongly NPhard, and derived a heuristic with a tight worst-case performance bound of 4/3. The heuristic constructs a schedule with at most three consistent batches. For the m-machine problems with identical processing time jobs and the criteria of minimizing P C j and C max , BIB020 suggested rounding procedures to calculate integer batch sizes from a straightforward solution of the relaxed non-integer batch size problem. BIB012 and BIB021 studied a continuous relaxation of the two-and m-machine problem, respectively, to minimize P C j with machine dependent setup and processing times and consistent batches. BIB012 suggested a solution method based on solving convex programming problems. The method provides an optimal solution for a certain combination of input parameters. BIB021 suggested an enumerative algorithm to construct the Pareto set for the simultaneous minimization of C max and P C j .  and BIB022 studied a two-stage problem, in which there is a single machine in the first stage and m machines in the second stage. Each job has to be processed on the first stage machine and then on a specific (dedicated) second stage machine. Thus, the jobs are classified into m families. The job processing time depends solely on its family index. A sequence independent setup time is required on the first stage machine to switch from a job of one family to a job of another family. The objective is to minimize the makespan. BIB022 showed that the problem can be solved in O(n m ) time and it can be solved in O(n log L) time for the two-machine case, where L is the maximum input parameter. The problem can be used for modeling a disassembly process. BIB001 considered a permutation flow shop in which the jobs of different families are processed in consistent batches under the batch availability model. The processing time of a batch is equal to the maximum processing time of its jobs. The setup times are anticipatory, family and machine dependent but sequence (of families) independent. Batch sizes are bounded from above by the same number. For minimizing C max and P w j C j , BIB001 suggested constructive heuristics and iterative algorithms, including simulated annealing, tabu search and multilevel search, based on specific neighborhood structures. A two-machine flow shop problem to minimize the makespan was studied by BIB009 under the group technology assumption, anticipatory sequence independent setup and removal times and limited intermediate buffer capacity c, 0 < c 6 n. Each job goes through the buffer when it moves from the first to the second machine. If the buffer is full, the job stays on the first machine, which prevents other jobs from being processed on this machine. The job processing times are family and machine dependent. Pranzo derived numbers b f , f = 1,. . . , F, such that if the cardinality of family f exceeds b f for each family, then the problem reduces to a polynomially solvable traveling salesman problem. BIB023 studied the single family problem AF2/ST si /C max with anticipatory, machine dependent batch setup times under the batch availability model. They proved that the search for an optimal schedule can be limited to permutation schedules and presented a heuristic with a tight worst case performance bound of 2 À 1/(m + 1). The heuristic constructs a schedule with one or two consistent batches. BIB013 considered a fabrication scheduling problem to minimize the makespan in a two-machine flowshop. Each job has a unique component and a common component to be processed on the first machine. On the first machine, the common components of the jobs are grouped into batches for processing with a setup cost incurred whenever a batch is formed. A job is ready for its assembly operation on the second machine if both its unique and common components are finished on the first machine. BIB013 proved that both problems of with batch availability and item availability are strong NP-hard. A two-machine flow shop problem to minimize the makespan was studied by BIB026 for the case where the first machine processes jobs individually and the second machine in batches under the batch availability model. Each batch is preceded by a constant anticipatory or non-anticipatory setup. The problem was proved to be strongly NP-hard. The case where the processing times on the two machines can be oppositely ordered is solvable in O(n 2 ) time. Constructive heuristics were presented for the general case.