A survey of scheduling problems with setup times or costs <s> Single machine <s> The majority of scheduling literature assumes that the machines are available at all times. In this paper, we study single machine scheduling problems where the machine maintenance must be performed within certain intervals and hence the machine is not available during the maintenance periods. We also assume that if a job is not processed to completion before the machine is stopped for maintenance, an additional setup is necessary when the processing is resumed. Our purpose is to schedule the maintenance and jobs to minimize some performance measures. The objective functions that we consider are minimizing the total weighted job completion times and minimizing the maximum lateness. In both cases, maintenance must be performed within a fixed period T, and the time for the maintenance is a decision variable. In this paper, we study two scenarios concerning the planning horizon. First, we show that, when the planning horizon is long in relation to T, the problem with either objective function is NP-complete, and we present pseudopolynomial time dynamic programming algorithms for both objective functions. In the second scenario, the planning horizon is short in relation to T. However, part of the period T may have elapsed before we schedule any jobs in this planning horizon, and the remaining time before the maintenance is shorter than the current planning horizon. Hence we must schedule one maintenance in this planning horizon. We show that the problem of minimizing the total weighted completion times in this scenario is NP-complete, while the shortest processing time (SPT) rule and the earliest due date (EDD) rule are optimal for the total completion time problem and the maximum lateness problem respectively. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 845–863, 1999 <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Single machine <s> We consider in this paper the single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties, where each time a job is started, whether initially or after preemption, a job-dependent setup must take place. First, we prove that the problem is strongly NP-hard. Then, we present a dynamic programming algorithm and a polynomial time approximation scheme. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Single machine <s> Extensive research has been devoted to preemptive scheduling. However, little attention has been paid to problems where a certain time penalty must be incurred if preemption is allowed. In this paper, we consider the single-machine scheduling problem of minimizing the total completion time subject to job release dates and preemption penalties, where each time a job is started, whether initially or after being preempted, a job-independent setup must take place. The problem is proved to be strongly NP-hard even if the setup time is one unit. We also study a natural extension of a greedy algorithm, which is optimal in the absence of preemption penalty. It is proved that the algorithm has a worst-case performance bound of 25/16, even when the maximum completion time, i.e., makespan, criterion is considered simultaneously. <s> BIB003
This section describes the setup time (cost) literature in a single machine environment, a summary of which is provided in Tables 1 and 2. 3.1. Non-batch sequence-independent setup times BIB001 addressed the problems 1/ST si /L max and 1=ST si = P w j C j where machine maintenance must be performed within certain intervals. They assumed that if a job is not finished before the next maintenance starts, then an additional setup is necessary when the remaining processing starts. They showed that both problems are NP-hard when the planning horizon is long, and they proposed pseudo-polynomial time dynamic programming algorithms for each problem. BIB002 considered the 1/ST si , pmtn, r j /D max problem where it was assumed that a certain setup time is incurred, which is job dependent, whenever a preempted job is restarted. They proved that the problem is strongly NP-hard (even if each setup time is one unit), and presented a dynamic programming algorithm to solve the problem. The dynamic programming has a pseudo-polynomial time requirement if the number of release dates is constant. BIB003 addressed the same problem but with the objective function of total weighted completion time, i.e., 1=ST si ; pmtn; r j = P w j C j , and with the assumption that setup times are constant and job independent. They proved that this problem is also strongly NP-hard, and proposed a greedy algorithm. They also proved that the algorithm has a worst-case performance bound of 25/16.