A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We consider a scheduling problem in which n jobs are grouped into F groups and are to be processed on a single machine. A machine setup time is required when the machine switches from one group of jobs to the other. All jobs have a common due date that needs to be determined. The objective is to find an optimal common due date and an optimal sequence of jobs to minimize the sum of the cost of tardy jobs and the cost related to the common due date. We consider two cases: 1.(i) the jobs have to be processed in groups; and 2.(ii) the jobs do not have to be processed in groups. Analytical results are presented and computational algorithms are developed. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> Abstract We review the current state of scheduling theory concerning the processing of several families of jobs on single or parallel facilities, where a setup time may be incurred whenever there is a switch from processing a job in one family to a job in another family. We also consider cases with the group technology assumption that the jobs must be scheduled contiguously. Using available results from the literature, we classify the different problems as NP-hard, efficiently solvable or open. We refine some old results and present several new ones. In particular, we show that under the group technology assumption, even with sequence-independent setup times, minimizing the number of late jobs on a single machine is NP-hard. We investigate the complexity of single machine scheduling with interfamily setup times, when we seek to minimize the maximal cost, where the cost for each job is a nondecreasing function of its completion time. We also prove that, when scheduling on parallel machines under the group technology assumption with sequence-independent setup times, minimizing total completion times is NP-hard unless all families contain the same number of jobs. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due date to minimize total weighted earliness and tardiness cost. Jobs are grouped into families where jobs in the same family share a setup; a setup time is required between the processing of two jobs from different families. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. These rates are assessed on a per-period basis when the completion time deviates from its due date. In this paper, we generalize properties from the literature that characterize the structure of an optimal schedule, present a lower bound, propose a branch and bound algorithm and a beam search procedure, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for smaller problem instances. For large problems, we find high quality solutions within a few minutes of CPU time. <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> In this paper we present an algorithm for the 2-weight batching problem: given n1 jobs with weight w1, and n2 jobs with weight w2, all having processing time p, and given a batch setup time Δ, find a sequence of batches of jobs such that the weighted sum of the n = n1 + N2 job completion times is minimized. The algorithm has running time O(n log n) when p and Δ are fixed; previously, the fastest known algorithm for this problem had running time O(n). Various properties of optimal solutions are exploited to reduce the problem to one of finding the minimum entry in a certain matrix. Since this matrix has some strong structural properties, its minimum entry can be found in time that is a sublinear function of the matrix size. <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> Abstract In a work center where multiple products have to be processed, setups may absorb a large part of the total time that is available for production of items and execution of setups. The fraction of time that the machine is busy (the total utilization) is the sum of the fraction of time spent on actual production (the productive utilization) and the fraction of time spent on setups (the setup utilization). By processing the items in batches one can save setups. When capacity is fixed, the setup utilization is fully determined by the batching decision. In practice, examples can be found where the setup utilization is used as a guide for making decisions on batch sizes. In those cases management sets a maximum on the fraction of time spent on executing setups. In this paper we will substantiate this procedure by studying a queueing delay batching model. When optimal batch sizes are used in the work center, the implied setup utilization is less than 0.175. As a consequence, whenever the setup utilization is higher than 17.5% the batch sizes can be improved in order to obtain shorter expected waiting times in the queue. <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> This paper considers a single machine group scheduling problem. All jobs are classified into groups and the jobs within a group are processed contiguously on the machine. A sequence-independent setup time is incurred between each two consecutively scheduled groups. This paper presents a solution procedure which utilizes Smith's algorithm and a proposed modified Smith's algorithm to find an optimal job sequence and an optimal group sequence which minimizes the mean flow time of jobs subject to the constraint that no jobs are tardy. The complexity of the algorithm is shown to have a polynomial running time in the number of groups and jobs. <s> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We propose and investigate a genetic algorithm for scheduling jobs about an unrestricted common due date on a single machine. The objective is to minimize total earliness and tardiness cost where early and tardy penalty rates are allowed to be arbitrary for each job. Jobs are classified into families and a family setup time is required between jobs from two different families. Results from a computational study are promising with close to optimal solutions obtained rather easily and quickly. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We investigate the single-machine sequencing problem in which each job has a processing time and a delivery time. The jobs are divided into families and a set-up time is incurred whenever there is a switch from a job in one family to a job in another family. This set-up only depends on the family of the job next to come and hence is sequence independent. The objective to to find a sequence of jobs that minimizes the time by which all jobs are delivered. The best polynomial-time approximation algorithm that was previously known for this problem is due to Zdrzalka and has a worst-case guarantee of 3 2. In this paper, we demonstrate the existence of a polynomial time approximation scheme for the problem. © 1998 John Wiley & Sons, Ltd. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> A single facility scheduling problem concerned with the production of jobs in a set of customer orders is analysed. Each order consists of several jobs. Based on the concept of group technology, jobs can be grouped into different classes. Jobs in the same class can be processed together in a combined batch, where batches of different classes are initiated with a setup time. Furthermore, the order availability is assumed, which means the finished jobs of an order cannot be shipped out to its customer until all other jobs in the same order have been completed. Under the above production environment, a branch-and-bound algorithm is developed to determine a schedule with the minimum mean flow time of orders. A heuristic is also developed to solve large-sized problems. Computational results of both approaches are reported. <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> This paper examines heuristic solution procedures for scheduling jobs on a single machine to minimize the maximum lateness in the presence of setup times between different job families. It reviews the state of knowledge about the solution of this problem, which is known to be difficult to solve in general, and examines natural solution approaches derived from some of the underlying theory. The emphasis is on the design and computational evaluation of new heuristic procedures. c 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 978{991, 1999 <s> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We consider the problem of allocating a single server to families of jobs with random service times and due dates. Furthermore, a set-up is required when the server switches from one job family to another. We address the problems of minimizing expected weighted flow time, expected maximum lateness, and total weighted tardiness with emphasis on problems for which it is assumed that each family can be set up only once (the Group Technology assumption). We derive conditions under which simple sequencing rules are optimal for each of these problems with group technology. <s> BIB011 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We study four scheduling problems involving the maximum lateness criterion and an element of batching. For all the problems that we examine, algorithms appear in the literature that consist of a sorting step to determine an optimal job sequence, followed by a dynamic programming step that determines the optimal batches. In each case, the dynamic program is based on a backward recursion of which a straightforward implementation requires O(n^2) time, where n is the number of jobs. We present improved implementations of these dynamic programs that are based on monotonicity properties of the objective expressed as a function of the total processing time of the first batch. These properties and the use of efficient data structures enable optimal solutions to be found for each of the four problems in O(nlogn) time; in two cases, the batching step is actually performed in linear time and the overall complexity is determined by the sorting step. <s> BIB012 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> Abstract. We study the problems of scheduling jobs, with different release dates and equal processing times, on two types of batching machines. All jobs of the same batch start and are completed simultaneously. On a serial batching machine, the length of a batch equals the sum of the processing times of its jobs and, when a new batch starts, a constant setup time s occurs. On a parallel batching machine, there are at most b jobs per batch and the length of a batch is the largest processing time of its jobs. We show that in both environments, for a large class of so called “ordered” objective functions, the problems are polynomially solvable by dynamic programming. This allows us to derive that the problems where the objective is to minimize the weighted number of late jobs, or the weighted flow time, or the total tardiness, or the maximal tardiness are polynomial. In other words, we show that 1|p-batch,b<n, ri, pi=p|F and 1|s-batch, ri, pi=p|F, are polynomial for F∈{∑wiUi,∑wiCi,∑Ti, Tmax}. The complexity status of these problems was unknown before. <s> BIB013 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We study the problem of scheduling jobs on a serial batching machine ::: to minimize total tardiness. Jobs of the same batch start and are ::: completed simultaneously and the length of a batch equals the sum of ::: the processing times of its jobs. When a new batch starts, a constant ::: setup time s occurs. This problem 1| s-batch | ∑ T i is ::: known to be NP-Hard in the ordinary sense. In this paper we show that ::: it is solvable in pseudopolynomial time by dynamic programming. <s> BIB014 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We consider the problem of scheduling n multi‐operationjobs on a single machine. Eachjob comprises up to F operations that belong to different families.Changeovers of production from one family to another have associated set‐up times.A job completes when all of its operations have been processed. This type of problem arisesin the manufacture of food products. It combines the batching aspect of the well‐knownfamily scheduling models with an assembly element (where the job's operationsare assembled to make the final product).Our analysis covers three classic optimality criteria: the maximum lateness, theweighted number of late jobs, and the sum of job completion times. We show that the problemof minimizing the maximum lateness is equivalent to its counterpart without assembly.This enables us to derive extensions of known complexity results and to indicate appropriatealgorithms. The number of late jobs problem is shown to be binary NP‐hard when thereare two families, and unary NP‐hard when there are an arbitrary number of families,even when all set‐up times are identical. For a fixed number of families, we give adynamic programming algorithm to minimize the weighted number of late jobs, which requirespseudo‐polynomial running time. A similar algorithm solves the sum of completion timesproblem in polynomial time, under the additional assumption that the processing times ofoperations between families are agreeable. Copyright Kluwer Academic Publishers 1999 <s> BIB015 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> Abstract This paper examines an optimal solution procedure for scheduling jobs on a single machine to minimize the maximum lateness in the presence of setup times between different job families. We exploit special structure to compress the effective problem size by creating composite jobs; then we accelerate the enumeration with dominance properties and lower bounds. Our computational evaluation highlights the size of setup times and the variation in due dates. <s> BIB016 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> This article presents initial results in the search for analytical models that can predict the performance of one-machine systems under periodic and event-driven rescheduling strategies in an environment where different job types arrive dynamically for processing and set-up must incur when production changes from one product type to another. The scheduling algorithm considered uses a first-in firstout dispatching rule to sequence jobs and it also groups jobs with similar types to save set-up time. The analytical models can estimate important performance measures like average flow time and machine utilization, which can then be used to determine optimal rescheduling parameters. Simulation experiments are used to show that the analytical models accurately predict the performance of the single machine under the scheduling algorithm proposed. <s> BIB017 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> SUMMARY A recent trend in the analysis of scheduling models integrates batching decisions with sequencing decisions. The interplay between batching and sequencing reects the realities of the small-volume, high-variety manufacturing environment and adds a new feature to traditional scheduling problems. Practical interest in this topic has given rise to new research eorts, and there has been a series of articles in the research literature surveying the rapidly developing state of knowledge. Exam- ples include Ghosh (1), Liaee and Emmons (2), Potts and Van Wassenhove (3), and Webster and Baker (4). This paper deals with an important theoretical and practical problem in this area. We examine the single-machine model with family (or group) set-up times and a criterion of minimizing total weighted job completion time (weighted owtime). We propose new lower bounds for this problem, and then turn our attention to renement of a previously proposed branch-and-bound algorithm. The benets of our renements are illustrated by computational experiments. <s> BIB018 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <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> BIB019 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> Abstract A model for real-time control of flexible manufacturing systems is considered. In this model, a machine can process a finite number of part types at specified rates, but only one part type can be processed at any given time. Each switch from one type to another requires setup time. The clear-the-largest-work-after-setup (CLWS) heuristic policy which stabilizes the system in the sense that, in the long run, the required demand is met, has been introduced. That way, a better upper bound on the total work backlog than those available in earlier literature is derived. Computational results for the case of finite horizon show that the error of the heuristic CLWS from the optimal solution is 2.5–3.0% on average. Some computational results that compare the CLWS heuristic to the heuristic available in the earlier literature, for the same problem, are also reported. <s> BIB020 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> The single-machine sequence-independent class setup scheduling problem is examined in this paper. It is assumed that jobs are classified into classes and a setup is required between jobs of different classes, but not of the same class. Furthermore, this setup time is fixed and depends only on the current job. Since the problem is NP-hard, a heuristic algorithm is proposed to find an approximate schedule that minimizes the maximum lateness on a set of jobs. The algorithm can easily be modified to solve the maximum tardiness problems as well. The accuracy of the heuristic algorithm in generating near optimal solutions is empirically evaluated. Scope and purposeFor batch manufacturing, it maybe desirable to produce many items of the same type, or class, at the same run in order to save the setup cost. However, committing facilities to long production runs for one product may inevitably make others tardy. Small batch size may conform urgent jobs to their delivery date, but one of the consequences would be the loss of productive efficiency due to numerous setups. Therefore, scheduling is basically a trade-off between the inherently conflicting efficiency measure and due-date compliance. This paper considers a single-machine scheduling problem in which jobs are classified into classes and a setup is required between jobs of different classes. The setup time is fixed and depends only on the current job. This problem is called a sequence-independent class setup problem and is NP-complete. <s> BIB021 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and processing times are one unit. Copyright © 2001 John Wiley & Sons, Ltd. <s> BIB022 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> Abstract Jobs are processed by a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource, which may be different from that for the jobs. Polynomial time algorithms are presented to find an optimal batch sequence and resource values such that either the total weighted resource consumption is minimized, subject to meeting job deadlines, or the maximum job lateness is minimized, subject to an upper bound on the total weighted resource consumption. The algorithms are based on linear programming formulations of the corresponding problems. <s> BIB023 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both... <s> BIB024 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We study a problem of scheduling customized jobs on a single-machine. Each job requires two operations: one standard and one specific. Standard operations are processed in batches under item availability, and each batch requires a set-up time. Based on structural properties of the optimal solution, we introduce a generic dynamic programming scheme that builds an optimal schedule by alternately inserting blocks of operations of two distinct types. Our approach yields efficient algorithms for the sum of completion times problem with agreeable processing times and the maximum lateness problem. The number of late jobs problem is shown to be NP-hard in the ordinary sense, but is pseudo-polynomially solvable. A polynomial algorithm is also given for a special case of this problem. Our results indicate the differences between this problem and its counterpart under batch availability. <s> BIB025 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> In view of the properties of multi-product batch scheduling problem with major and minor setup times that a practical steel pipe plant of iron and steel industry usually has, a 0-1 mixed integer-programming model to the problem is developed with minimizing the job maximum lateness (L/sub max/) as the optimal objective function. A tabu search-based heuristic (TSH) algorithm is proposed by analyzing the optimal properties of the problem. The simulation results have confirmed its feasibility and effectiveness. <s> BIB026 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We consider the single machine, serial batching, maximum lateness scheduling problem with precedence constraints in this paper. The complexity of this problem is reported as open in the literature. We give an O(n^2) polynomial-time algorithm for this problem. <s> BIB027 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> Abstract There is a fabrication machine available for processing a set of jobs. Each job is associated with a due date and consists of two parts, one is common among all products and the other is unique to itself. The unique components are processed individually and the common parts are grouped into batches for processing. A constant setup time is incurred when each batch is formed. The completion time of a job is defined as the time when both of its unique and common components are completed. In this paper, we consider two different objectives. The first problem seeks to minimize the maximum tardiness, and the second problem is to minimize the number of tardy jobs. To minimize the maximum tardiness, we propose a dynamic programming algorithm that optimally solves the problem in polynomial time. Next, we show NP-hardness proof and design a pseudo-polynomial time dynamic programming algorithm for the problem of minimizing the number of tardy jobs. <s> BIB028 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We consider the single machine multi-operation jobs total completion time scheduling problem. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a set-up time. A job completes when all of its operations have been processed. The objective is to minimize the sum of the job completion times. In the literature, the computational complexity of this problem is posed as open. We show that the problem is strongly NP-hard even when the set-up times are common and the processing time of each operation is 0 or 1. <s> BIB029 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We examine the problem of scheduling jobs, on a single processor to minimise the total earliness and tardiness costs about a common due date. Jobs belong to mutually exclusive families and a sequence independent setup task is required when processing switches from a job of one family to a job of another.We extend earlier results to obtain necessary optimal conditions for this problem. These are then used to generate a fast heuristic. Its performance is compared with a lowerbound, a greedy heuristic, a genetic algorithm and for small problems, the optimal solution. <s> BIB030 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We consider the single machine, serial batching, total completion time scheduling problem with precedence constraints, release dates and identical processing times in this paper. The complexity of this problem is reported as open in the literature. We provide an O(n^5) time algorithm to solve this problem. <s> BIB031 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. While the problem was proved to be binary NP-hard in 1978, whether the problem is strongly NP-hard is a long-standing open question. We show that this problem is strongly NP-hard. <s> BIB032 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time. <s> BIB033 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n3 log n) and O(n5) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems. <s> BIB034 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> Abstract In this paper we consider the problem of creating batches of parts, to be processed in a flexible manufacturing cell, and scheduling their operations. We consider the case in which the system consists of one machine and at most k parts may be present in the system at the same time. Given that each part requires a sequence of operations, and each operation requires a given tool, the objective is to minimize the total number of setups. We develop a heuristic algorithm for its solution and we present an extensive computational experience. <s> BIB035 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> A procedure for the single machine-scheduling problem of minimizing the maximum lateness for jobs with sequence independent set-ups is presented. The procedure provides optimal/near-optimal solutions over a wide range of problems. It performs well compared with other heuristics, and it is effective in finding solutions for large problems. <s> BIB036 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +∞, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time. <s> BIB037 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> We apply group technology on a single-facility scheduling problem of products assembled from common and unique components. Our model assumes that common components are classified into multiple families, whose set-up times are sequence-independent but not identical. This extension from one type of common components to multiple types distinguishes this study from those in the literature. After identifying properties for dominant schedules, a branch-and-bound algorithm is constructed to determine a production schedule with the minimum total completion time of products. A series of simulation experiments are made with respect to the number of families and the number of products. The outcome may provide a foundation for future research on this topic. <s> BIB038 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> Abstract A single machine batch scheduling problem is addressed. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Two external resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource and the job processing times are jointly compressible by another resource, i.e., the amount of resource consumption for setup time compression is the same for all setups and the amount of resource consumption for job processing time compression is the same for all jobs. Polynomial time algorithms are presented to find an optimal batch sequence and optimal amounts of resource consumption such that either total job completion time is minimized, subject to an upper bound on total weighted resource consumption, or total weighted resource consumption is minimized, subject to an upper bound on total job completion time. The algorithms are based on results from linear programming and from batch scheduling with fixed setup and processing times. <s> BIB039 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> It is a basic scheduling problem to sequence a set of precedence-constrained tasks to minimize the number of setups, where the tasks are partitioned into classes that require the same setup. We prove a conjecture in (Ph.D. Thesis, School of ISyE, Georgia Institute of Technology, August 1986; Oper. Res. 39 (1991) 1012) that no polynomial-time algorithm for this problem has constant worst-case performance ratio unless P = NP. A very simple algorithm has performance ratio √n. <s> BIB040 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> A single machine scheduling problem is studied. There is a partition of the set of n jobs into g groups on the basis of group technology. Jobs of the same group are processed contiguously. A sequence independent setup time precedes the processing of each group. Two external renewable resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource, the job processing times are jointly compressible by another resource and the level of the resource is the same for all setups and all jobs. Polynomial time algorithms are presented to find an optimal job sequence and resource values such that the total weighted resource consumption is minimum, subject to meeting job deadlines. The algorithms are based on solving linear programming problems with two variables by geometric techniques. <s> BIB041 </s> A survey of scheduling problems with setup times or costs <s> Polynomial algorithms <s> The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence independent setup time preceding the processing of each group. The setup times and the job processing times are controllable through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource. Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming. <s> BIB042
3.3. Batch sequence-independent setup times BIB001 considered the 1/ST si,b problem with the objective of obtaining the optimal common due date and the optimal sequence of jobs to minimize the common due date cost (which is linearly related to the length of common due date) and the sum of the costs of tardy jobs. They addressed problems with and without the group technology assumption. For both cases, they presented properties of the optimal solutions, and they proposed algorithms to solve each problem in polynomial time. Several authors addressed the 1/ST si,b /L max problem.  developed several dominance properties and lower bounds, and utilized the properties and lower bounds in a branch-andbound algorithm to solve the problem. BIB016 pointed out that the problem size that can be solved depends on several factors such as the number of batches, the number of jobs in each batch, due date range, and setup factor. BIB021 formulated the problem as an integer program and proposed a heuristic to solve the problem. BIB010 considered the case where the setup times are the same for different job families. He proposed and compared several heuristic procedures for the problem. The branch-and-bound algorithms of  , and BIB016 remain to be compared, as well as the heuristics of BIB010 and BIB021 . BIB026 modeled a practical steel pipe plant as the 1/ST si,b /L max problem with the group technology assumption, where the jobs are a priori partitioned into classes and the classes are grouped into families. A major setup occurs when the jobs are switched from one family to another, while a minor setup occurs when the jobs are switched from one class to another within the Soric (2000a,b) Average work backlog (dynamically arriving jobs) On-line heuristic, MILP formulation, cutting plane branch-and-bound algorithm BIB017 Average flowtime, machine utilization, setup frequency, rescheduling frequency (stochastic environment with machine breakdowns, dynamically arriving jobs) Rescheduling algorithm same family. They provided an integer programming formulation for the problem and proposed a tabu search-based heuristic. The 1=ST si;b = P U j problem was shown to be NP-hard in the strong sense by BIB022 even for the case where all the setup times and processing times are one unit. proved that this problem is strongly NP-hard under the group technology assumption, with unit processing times and zero setup times. The NPhardness of the problem with the group technology assumption was also established by BIB002 . BIB006 considered the 1=ST si;b = P f j problem under the group technology assumption and the assumption that all the jobs are ready for processing at time zero. They proposed an algorithm to solve the problem, subject to the constraint that no jobs are tardy. The complexity of the algorithm is shown to have a polynomial running time in the number of groups and jobs. The 1=ST si;b = P w j f j problem was addressed by BIB018 where it is assumed that all the jobs are available from time zero. They developed lower bounds and incorporated these lower bounds into a branch-and-bound algorithm. Their algorithm is quite efficient since problems up to 70 jobs can be solved optimally within a reasonable time. Yang and Chand (in press) addressed the 1=ST si;b = P C j problem, where the setup time of a batch is characterized by a learning factor and changes based on its position in a schedule. They developed two lower bounds, and implemented these lower bounds in a branch-and-bound algorithm. They concluded that the influence of learning on group scheduling increases with the speed at which a family accumulates experience. BIB003 proposed a branchand-bound algorithm to solve the 1=ST si;b = P w j E j þ P w j T j problem with a common due date. They solved problems with up to 20 jobs and pointed out that problem size and weight combinations play a dominant role in the difficulty of obtaining optimal solutions. For large-sized problems, they presented a beam search procedure, which has a parameter by which a trade-off between the error and computation time can be made. BIB007 proposed a genetic algorithm for the same problem. The results of their computational experiments showed that the algorithm converges close to optimal solutions quickly. BIB030 provided several necessary conditions for a solution to be optimal. They also proposed a greedy heuristic and a genetic algorithm for the problem. The 1/ST si,b /D max problem was addressed by BIB008 , where each job has a delivery time. The best previously known polynomial time approximation algorithm for this problem has a worst-case guarantee of 3/2. Woeginger (1998) demonstrated the existence of a polynomial time approximation scheme for the problem.  studied the 1/ ST si,b , SC si,b problem with a sum of regular objective functions. The jobs may have different release dates and deadlines. They developed lower bounds and dominance properties, and proposed a branch-and-bound algorithm, which was evaluated experimentally. The problem of 1=ST si;b = P T j was considered by Schaller (in press), where he proposed a branchand-bound algorithm for the problem with and without the group technology assumption. He also proposed a heuristic to solve larger-sized problems. His computational experiments revealed that total tardiness can be significantly reduced by removing the group technology assumption. He solved problems with up to 10 families and 20 jobs in each family. Schaller and Gupta (in press) studied the same problem with the objective of 1=ST si;b = P E j þ P T j by following the same procedure. All the job characteristics are assumed to be deterministic in all of the above literature. BIB011 addressed the problems of 1=ST si;b =L max ;1=ST si;b = P w j f j , and 1=ST si;b = P w j T j , where the processing times and due dates are random variables, and the criterion is to minimize the expected value of the objective function. They considered the problem with and without the group technology assumption and derived conditions under which simple sequencing rules are optimal for each problem. Assuming that all the jobs are ready at time zero,  considered the 1=ST si;b = P f j problem, where there are families of jobs and each family is partitioned into classes. A major setup time is required when processing is switched from one family to another, while a minor setup time is necessary when it is switched from one class to another. They proposed a tabu search algorithm for the problem and showed by computational analysis that their proposed algorithm performs better than the existing dynamic programming based heuristic. Yuan et al. (in press-a) showed that the 1/ ST si,b , r j /C max problem is strongly NP-hard even if the processing times of the jobs are unit and the setup times of the families are identical. They provided two dynamic programming algorithms, a heuristic with a performance ratio of 2, and a polynomial-time approximation scheme for the problem. BIB035 addressed a problem in which the jobs of the same family are processed in batches of the same size, each batch is preceded by a constant setup time and every job within each batch needs a sequence of specific tools, in which the tools can be repeated. A (super)sequence of all the required tools is loaded before the batch is processed. Each job uses a subsequence of the tools in this supersequence. The tools are used in parallel. The number of setups inside a batch is equal to the length of the corresponding tool supersequence minus one. The problem is to partition the jobs into the batches and, for each batch, determine a supersequence of the required tools such that the total number of setups is minimized. The authors suggested a heuristic algorithm for this problem. BIB012 proposed an O(n log n) dynamic programming algorithm for a single family problem to minimize L max under the batch availability model. BIB027 demonstrated that this problem with precedence constraints reduces in O(n 2 ) time to the one without precedence constraints. A single family problem with equal job processing times and arbitrary job release dates was studied by BIB013 under the batch availability model and non-anticipatory setups for various regular objectives. Dynamic programming algorithms of O(n 14 ) running time were derived for minimizing P w j U j , P w j C j and P T j , and T max was minimized in O(n 14 log n) time. BIB031 improved this result for the P C j objective by presenting an O(n 5 ) time algorithm even if there are precedence constraints.  showed that the above problem to minimize L max with precedence constraints reduces in O(n 2 ) time to the one without precedence constraints. For a single family problem with equal job processing times and common setup time to minimize P C i under the batch availability model, suggested an O(n) rounding procedure to calculate integer batch sizes from a straightforward solution of the relaxed non-integer batching problem. Mosheiov and Oron (in press-a) extended these results to the case where batch sizes are bounded from below or above. BIB014 suggested a pseudopolynomial dynamic programming algorithm for a single family problem to minimize the total tardiness. BIB023 developed polynomial time algorithms for two single family problems with job processing times and setup times dependent on two different uniform resources. The batch availability model was considered. In one problem, the objective is to minimize the total weighted resource consumption, subject to meeting job deadlines, and in the other problem, the objective is to minimize L max , subject to an upper bound on the total weighted resource consumption. The algorithms are based on solving an integer linear program with two variables. BIB024 studied a single family problem under the batch availability model for various objective functions. Properties of optimal schedules were established and polynomial-time dynamic programming algorithms were derived for the cases where there are a constant number of distinct processing times or a constant number of distinct due dates. The same model was considered by BIB004 , where the job processing times are all equal and the job weights take at most two distinct values, and the objective is to minimize P w j C j . An Oð ffiffi ffi n p log nÞ time algorithm was suggested. BIB032 proved the strong NP-hardness of the problem 1/ST si,b /L max . BIB036 proposed a neighborhood search heuristic for this problem. BIB037 presented a 2-approximation algorithm for a single family problem, in which the setup time for a batch is given by the maximum job setup time in this batch and the processing time of a batch is given by the maximum job processing time in this batch. The objective is to minimize the total weighted completion time. Computational complexity of this problem is unknown. Yuan et al. (in press-b) addressed the 1=ST si;b ¼ s= P w j C j (where ST si,b = s means constant setup times) problem with the restriction that each batch contains the same number of jobs (called the batch size). They proved that this problem is strongly NPhard even if the batch size is 3 and the weight of each job is equal to its processing time. O(n log n) time algorithms were given for two special cases of the problem. BIB019 studied a problem in which each job consists of two components: standard and specific. 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 its components have been completed. For any regular objective function, Gerodimos et al. proved that there exists an optimal schedule in which the specific components of the jobs in the same batch (of standard components) immediately follow this batch. Therefore, the problem reduces to finding a sequence of specific components and its partition into subsequences corresponding to the batches of standard components. The earliest due date (EDD) sequence was proved to be optimal for L max minimization and for the early jobs in case of P U j minimization. The latter problem was proved to be NP-hard. Both problems were solved by dynamic programming algorithms in O(n 2 ) and O(n 2 d max ) time, respectively, where d max is the maximum due date. Wagelmans and Gerodimos (2000) improved the algorithm for L max minimization to have O(n log n) time complexity. BIB038 generalized the model of BIB019 by assuming that the common components belong to several families and a sequence independent setup time precedes a batch of such components. For P C j minimization, Yang gave some properties of an optimal solution and suggested a branch-and-bound algorithm, which was shown to be able to solve problems with up to 5 families and 40 jobs in each family. BIB025 and BIB028 studied a problem differing from the problem of BIB019 in that the job availability model is applied for the batch processing of the standard components. For L max and P U j minimization problems, BIB025 obtained the same results as those under the batch availability model with respect to computational complexity. Furthermore, an O(n log n) time algorithm was developed for the problem of minimizing P C j in the case of agreeable processing times between the standard and specific operations (they can be similarly ordered). These results outperformed those of BIB028 . BIB015 studied a problem in which each job consists of up to F operations belonging to different families. A job is completed when all its operations have been processed. A sequence independent setup time occurs between the operations of different families. Like under the job availability model, operations are completed individually. The problem of minimizing L max was shown equivalent to the problem 1/ST si,b /L max . Therefore, it is NP-hard in the strong sense and solvable in polynomial time for any fixed F. Minimization of P U j was proved to be NP-hard in the strong sense and pseudopolynomially solvable for any fixed F. BIB033 proved that this problem of minimizing P U j remains strongly NPhard even if the due-dates are the same and all the jobs have the same processing time. BIB029 proved that the problem of minimizing P C j is strongly NP-hard even if the setup times are the same and each operation processing time is 0 or 1. It is polynomially solvable if the operation processing times are all agreeable and F is fixed BIB015 . BIB009 suggested a branch-andbound algorithm for a problem in which each job is attributed to a family and an order. There is a sequence independent setup time between the jobs of different families. An order is completed upon the completion of its latest job. The objective is to minimize the total order completion time. Problems up to 24 jobs were solved by the branch-and-bound algorithm. Multiple family problems were studied by BIB041 and BIB042 under the group technology assumption with resource dependent setup and processing times. It is assumed that the same amount of one resource is assigned to all the setups and the same amount of another resource is assigned to all the jobs. The resources can all be continuously divisible or all discrete. BIB041 presented polynomial-time algorithms based on geometric techniques to minimize the total weighted resource consumption provided that the job deadlines are met. BIB042 derived polynomial-time algorithms to minimize P w j C j , subject to an upper bound on the total weighted resource consumption. A key element of the algorithms is a reduction to solving a linear programming problem with two variables. A similar solution approach was used by BIB039 to handle a single family problem under the batch availability model. Polynomial-time algorithms were derived for minimizing P C j , subject to an upper bound on the total weighted resource consumption and an inverse problem (minimizing the total weighted resource consumption, subject to an upper bound on P C j ). BIB034 extended the model of BIB039 by allowing job and batch dependent resource consumptions. They mentioned that the computational complexity of the problem of minimizing P C j , subject to an upper bound on the total weighted resource consumption, is unknown and developed-polynomial time algorithm for this problem and an inverse problem in the case where lower and upper bounds on the job processing times are agreeable (can be similarly ordered). Soric (2000a,b) and BIB017 studied a problem with dynamically arriving jobs belonging to a fixed number of families. There is a constant setup time s between the jobs of different families. Soric considered the objective of minimizing the average work backlog. In the case of an infinite number of jobs, BIB020 suggested an on-line heuristic called Clear-the-Largest-Work-afterSetup, which chooses for production at a decision time point t a family with the largest work backlog at time t + s. If a family is chosen for production, all the jobs of this family having arrived so far are produced. In the case of a finite number of jobs, Soric (2000b) developed a mixed integer linear programming formulation and a cutting plane branch-andbound algorithm. BIB017 considered a stochastic environment with machine breakdowns. They suggested a rescheduling algorithm and analytically compared its performance with respect to the average flowtime, machine utilization, setup frequency and rescheduling frequency under periodic and eventdriven rescheduling strategies. In their study, periodic rescheduling occurs every h time units, while event-driven rescheduling occurs when a new job arrives. The suggested algorithm groups unprocessed jobs of the same family into the same batch, dispatches jobs of the same batch according to the First-In-First-Out (FIFO) rule and dispatches batches according to the FIFO rule applied to the first jobs of the batches. BIB005 studied the effect of batch sizes on setup utilization (total setup time divided by total setup and processing time) in a queuing delay batching model. They established an upper bound of 3 À 2 p 2 % 0.175 on the optimal setup utilization. This result implies that batch sizes should be corrected if setup utilization is higher than 0.175 for the considered model. BIB040 considered the problem with multiple families and arbitrary precedence relations with the objective of minimizing the number of setups. He proved that the objective cannot be approximated in polynomial time with a constant worstcase performance ratio unless P = NP. Wang and Zou (2002) studied a steel pipe plant scheduling problem, where the jobs are partitioned into classes and the classes are grouped into families. A major setup time is required when jobs are switched from one class to another while a minor setup time is necessary when jobs are switched from one family to another within the same class. Under the group technology assumption with regard to families, BIB026 proposed a mixed integer programming, and presented a tabu search heuristic to solve the problem with respect to the maximum lateness criterion.