A survey of scheduling problems with setup times or costs <s> Notation and classification <s> The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Notation and classification <s> There is an extensive literature on models that integrate scheduling with batching decisions. Jobs may be batched if they share the same setup on a machine. Another reason for batching occurs when a machine can process several jobs simultaneously. This paper reviews the literature on scheduling with batching, giving details of the basic algorithms, and referencing other significant results. Special attention is given to the design of efficient dynamic programming algorithms for solving these types of problems. <s> BIB002
This section provides the necessary notation and classification for the scheduling problems with setup times/costs discussed in this paper. The definitions of batch and non-batch setup times (costs) are first introduced. A batch setup time (cost) occurs when jobs, e.g., machine parts, are processed in batches (pallets, containers, boxes) and a setup of a certain time or cost precedes the processing of each batch. The definition of a batch is as follows. The jobs are supposed to be partitioned into F, F P 1, families. A batch is a set of jobs of the same family. While families are supposed to be given in advance, batch formation is a part of the decision making process. An important special case appears when the Group Technology assumption has to be observed. According to this assumption, no family can be split, i.e., only a single batch can be formed for each family. The batch setup time (cost) can be machine dependent or sequence (of families) dependent. It is sequence-dependent if its duration (cost) depends on the families of both the current and the immediately preceding batches, and is sequence-independent if its duration (cost) depends solely on the family of the current batch to be processed. Batch setup models are further partitioned into batch availability and job availability models. According to the batch availability model, all the jobs of the same batch become available for processing and leave the machine together. In the job availability model, each job's start and completion times are independent of other jobs in its batch. We implicitly assume that the job availability model is considered, if it is not stated otherwise. For multistage processing systems, permutation and non-permutation schedules and schedules with consistent and inconsistent batches are distinguished. A schedule is a permutation schedule if the job sequences are the same on all the machines. The batches are consistent if batch formation is the same on all the machines. Opposite statements define a non-permutation schedule and inconsistent batches. In a non-batch processing environment, a setup time (cost) is incurred prior to the processing of each job. The corresponding model can also be viewed as a batch setup time (cost) model in which each family consists of a single job. We distinguish anticipatory or non-anticipatory setups. A setup is anticipatory if it can be started before the corresponding job or batch becomes available on the machine. Otherwise, a setup is non-anticipatory. If it is not stated explicitly that setups are non-anticipatory, we assume that they are anticipatory unless there are job release dates, in which case a setup cannot start before the corresponding release date. In setup time models, no job processing is possible on a machine while a setup is being performed on the machine. We use a similar classification of setup time (cost) problems adopted in the survey paper by Allahverdi et al. (1999) . The terminology ''family'' adopted by BIB002 is used in the current survey to denote initial job partitioning, while the terminology ''batch'' is used to denote a part of the solution. It should be noted that many publications use the terminology ''batch'' to denote the initial job partitioning and they use different names like sub-batch, lot, sub-lot, etc., to denote a set of jobs of the same family processed consecutively on the same machine. This terminology was adopted by Allahverdi et al. (1999) (Fig. 1) . We adapt the three-field notation a/b/c of BIB001 to describe a scheduling problem. The a field describes the shop (machine) environment. The b field describes the setup information, other shop conditions, and details of the processing characteristics, which may contain multiple entries. Finally, the c field contains the objective to be minimized. For example, a three-machine flow shop scheduling problem to minimize maximum lateness with batch sequence-dependent setup times will be noted as F3/ST sd,b /L max . Shop type (a field) 1 single machine F flow shop FF flexible (hybrid) flow shop AF assembly flow shop P, Q, R parallel machines (P: identical machines; Q: uniform machines; R: unrelated machines) Shop characteristics (b field) prec precedence constraints r j non-zero release date pmtn preemption