4OR-Q J Oper Res (2009) 7:37–50 DOI 10.1007/s10288-007-0061-5 RESEARCH PAPER

Single machine scheduling with forbidden start times Jean-Charles Billaut · Francis Sourd

Received: 12 December 2006 / Revised: 12 October 2007 / Published online: 7 November 2007 © Springer-Verlag 2007

Abstract This paper addresses a single machine scheduling problem in which the following simple constraint is added: a set of time slots is forbidden for starting a task, that is no task can start at any forbidden time point. We show that the single machine problem with makespan minimization is strongly N P-complete and we give polynomial algorithms to solve the problems with a small number of forbidden start times. Keywords One machine scheduling · Unavailability MSC classification (2000) 90B35 · 90C39 1 Introduction When considering a scheduling problem, it is generally assumed that the resources are always available for processing the tasks. Sometimes some unavailability periods are considered, that is periods during which no task can be processed. In these problems, a task can either start before the period and resume after the period (resumable case), or must be completely scheduled between two unavailability periods (non-resumable case). The main scheduling problems with unavailability periods have already been considered in the literature, (Lee 1996,1999; Gharbi and Haouari, 2005;

J.-C. Billaut Laboratoire d’Informatique, Université François-Rabelais de Tours, 64 avenue Jean Portalis, 37200 Tours, France e-mail: [email protected] F. Sourd (B) LIP6, CNRS, Université Pierre et Marie Curie, 4 place Jussieu, 75252 Paris cedex 05, France e-mail: [email protected]

123

38

J.-C. Billaut, F. Sourd

Mauguière et al. 2005). A recent overview can also be found in the book chapter of Lee (2004). However, while most theoretical scheduling literature focuses on the resumable and non-resumable cases, real-life unavailability periods may cause a large bunch of different types of constraints, as it is illustrated by the Application Programming Interface (API) of ILOG Scheduler (2003). In particular, some unavailability periods may prevent to launch or stop a task during a given period but a running task is not necessarily interrupted by periods of this type. In the problem we study, the tasks have integral processing times and a given set of integral forbidden start times is given. It means that no task can have a start time belonging to this set. For instance, in a workshop, the forbidden start times can correspond to the dates at which the operators have to receive raw materials-and thus cannot be present at the same time in front of the machines for starting a new task. In multi-machine environments, assuming a single operator is qualified for performing a machine setup, this operator cannot perform all the setups at the same time even if the setup time is small. Therefore two operations cannot start at the same time, here the forbidden start times would correspond to the time slots where the operator is known to be busy. Formally we are given a set J = {J1 , J2 , . . . , Jn } of n tasks to be scheduled on a single machine. To each task J j is associated a processing time p j . We denote by
k Pk = i=1 pi , P0 = 0 and P = Pn . It is assumed that the tasks start at integral time points and that some start times are forbidden. We denote by F = {F1 , F2 , . . . , FK } the set of the K forbidden start times and we assume without loss of generality that 0 < F1 < F2 < · · · < FK . The problem is to schedule the tasks so that no task starts at a forbidden start time and so that the makespan is minimum. Formally, if a schedule is given by the start times S1 , . . . , Sn , the “forbidden-start-times” constraint is defined by / F, ∀ j, 1 ≤ j ≤ n. (1) Sj ∈ In some classes of instances where there are several adjacent forbidden start times, the input can be more compactly encoded using the concept of “forbidden intervals”: a task cannot start in a forbidden interval, but it can be in process or completed in such an interval. The concept of “forbidden interval” is closely related to the concept of unavailability period. However, we emphasize the difference that the processing of a task is not restrained by the presence of forbidden start times while the task has started at a non-forbidden start time. Constraints (1) imply that the setup period of each task is unary, that is the constraints / F. In some cases, the setup periods may be of length p > 1, that only check that S j ∈ is p j ≥ p for all j and we must have {S j , S j + 1, . . . , S j + p − 1} ∩ F = ∅ for all j. We can show that this problem is equivalent to the problem with forbidden start times with an extended set of forbidden start times equal to F  = ∪ f ∈F { f − p + 1, . . . , f }. In other words, the problem with equal setup periods is equivalent to the problem with unit setup periods. In an optimal schedule, the “forbidden start times” constraints may give rise to the insertion of idle times in the schedule. Therefore, the problem is to minimize the number of idle slots. The problem can be denoted by 1|S j ∈ F|Cmax in the well-known

123

Single machine scheduling with forbidden start times

39

three-field α|β|γ notation, where S j ∈ F corresponds to the constraint of forbidden start times. In the literature, some works have considered scheduling problems with discrete sets of allowed start times. In other words, the constraints write S j ∈ F j for all j where F j is the set of possible start times for task j. The model was introduced by Nakajima and Hakimi (1982) in a parallel machine environment. They proved the problem is N P-complete. Keil (1992) studies the one-machine problem. Rosenkrantz (2001) studies the one-machine and parallel machines problems when the tasks are subject to release dates. The rest of the paper is organized as follows. We consider the general problem and show its strong N P-hardness in Sect. 2. Then we study polynomially solvable cases for small values of K . Section 3 is devoted to the case where K = 1 and Sect. 4 to the case where K = 2. Finally, Sect. 5 presents a dynamic programming algorithm that is polynomial when K is considered as a constant. 2 Study of the general problem We consider the decision problem to determine whether a schedule without idle time— that is a schedule with makespan P—exists or not. We denote this problem by SMSFST, formally defined by: SMS-FST (Single Machine Scheduling with Forbidden Start Times): Data: J a set of tasks, p j processing time of task J j , a set of forbidden start times F, |F| = K . Question: does a schedule of all the tasks exist on a single machine, with a makespan equal to P and no start time in F? Theorem 2.1 SMS-FST is N P-complete in the strong sense. Proof The problem is clearly in N P. To prove the theorem we give a pseudopolynomial transformation from 3-PARTITION to SMS-FST. Since 3-PARTITION is strongly N P-complete, then so is SMS-FST (Garey and Johnson 1979, Lemma 4.1). 3-PARTITION is formally defined by: Data: a finite set A of 3m elements, a bound
B > 0 and a size s(a) for each a ∈ A that satisfies B/4 < s(a) < B/2 and a∈A s(A) = m B. Question: Can A be partitioned
into m disjoint sets S1 , . . . , Sm such that, for each i ∈ {1, . . . , m}, we have a∈Si s(a) = B? We build an instance of SMS-FST with n = 4m tasks defined as follows: • •

the first 3m tasks correspond to the elements of A: the task associated with a has a processing time equal to s(a). m tasks T1 , T2 , . . . , Tm with a processing time equal to B.

The number of forbidden  start times is equal to K = m(B −1). The set of forbidden start times is given by F = 1≤i≤m [(2i − 1)B + 1, 2i B − 1], that is we periodically have B + 1 allowed start times followed by B − 1 forbidden start times (see Fig. 1): F1 = B +1, F2 = B +2, . . . , FB−1 = 2B −1, FB = 3B +1, etc. This transformation

123

40

J.-C. Billaut, F. Sourd B B

0

T1 F1

B B

F1 + B − 2

T2

B B

B B

Tm FK

Fig. 1 Instance of problem SMS-FST

of the instance of 3-PARTITION is pseudo-polynomial since the number of forbidden start times depends on B. We want to schedule all the tasks without idle slots, that is the schedule is to be completed at time 2m B. In order that the time slot [2i B − 1, 2i B] is not idle, a task of length at most B must be started at (2i − 1)B or before, which means that it must be a task of length B that starts at (2i −1)B. Therefore, in a schedule without idle time, task Ti of length B has to start at time (2i − 1)B for i ∈ {1, . . . , m}. If there is no idle time in the schedule, the 3 m remaining tasks are scheduled in the m remaining intervals of length B, which gives a solution to 3-PARTITION. Conversely, any solution to 3-PARTITION clearly leads to a schedule without idle time. 

This reduction shows that, unless P = N P, the problem has no constant-factor approximation algorithm. Indeed, if we have a forbidden interval [2m B, T ], finding a schedule that completes before T is as difficult as finding a schedule that completes before 2m B. However an obvious upper bound for any feasible schedule is P + |F|, which means that any algorithm that schedules tasks in an arbitrary order as soon as possible has an absolute performance guarantee of |F|. If we assume that the problem has only one interval of forbidden start times, a similar reduction based on PARTITION shows that the problem is N P-complete in the ordinary sense. We can also show that this problem can be solved in pseudo-polynomial time by adapting the classical dynamic programming algorithm for PARTITION. In the following sections, we are going to show that if there are only one or two forbidden start times, the problem becomes polynomial and that it remains polynomial when K is assumed to be a constant. Before, we show that the case where all the tasks are identical ( p j = p for all j) can also be solved in polynomial time. Theorem 2.2 Problem 1|S j ∈ F, p j = p|Cmax can be solved optimally in O(K ) time, assuming that the forbidden start times are given in increasing order. Proof In this case, all the tasks are identical and thus there is no sequencing problem. The only problem is to assign a start time not in F to each task. If no forbidden start time is equal to 0 (mod p) the tasks can be sequenced without introducing an idle time. Otherwise, one idle time has to be introduced and if no remaining forbidden start time is equal to 1 (mod p), the tasks can be sequenced without introducing an idle time. The process iterates K times and finally returns the optimal makespan value. The procedure given in Fig. 2 returns the optimal makespan in O(K ). 

123

Single machine scheduling with forbidden start times

41

1. C = P ; t = 0; i = 1 2. while i ≤ K and Fi < C do if Fi ≡ t (mod p) then C = C + 1; t = t + 1 endif i=i+1 3. return C

Fig. 2 Optimal procedure for the 1|S j ∈ F , p j = p|Cmax problem

3 One forbidden start time Theorem 3.1 If K = 1, there exists an optimal schedule of makespan equal to P unless pi = p for all tasks and F1 = kp for some integer k < n. In the latter case, the makespan is equal to P + 1. Proof If the processing times of all tasks are equal to p and F1 = kp, there clearly exists no feasible active schedule that completes at P = np. Indeed in such a schedule, the k + 1th task would start at time kp, which is forbidden. Conversely, we can obviously build a schedule that completes at P +1 by starting the k +1th task at time kp+1. We now show that in any other case, there is a schedule which completes at P. If the processing times of all tasks are equal to p and F1 = kp, each task starts at time kp (with 0 ≤ k ≤ n −1) and so any sequence is feasible and completes at P. If there are at least two different tasks to schedule, we can assume without loss of generality that p1 = p2 and that p1 ≥ pi for all i. Let k be the index such that Pk−1 ≤ F1 < Pk . Therefore, we have Pk − F1 ≤ pk ≤ p1 . If Pk − F1 < p1 , we can schedule the tasks J2 , . . . , Jk in any order between 0 and Pk − p1 < F1 and J1 between Pk − p1 and Pk . If Pk −F1 = p1 , we can schedule the tasks J3 , . . . , Jk in any order between 0 and Pk − p1 − p2 < F1 and J1 between Pk − p1 − p2 and Pk − p2 = F1 + p1 − p2 = F1 . Therefore, J2 can start at Pk − p2 . In both cases, we are able to schedule J1 , . . . , Jk before Pk and all 

the other tasks can be scheduled later in any order to complete before Pn . The above proof gives an O(n) algorithm to build an optimal schedule when there is only one forbidden start time and at least two different tasks to schedule. 4 Two forbidden start times In this section, we assume that K = 2 and 0 < F1 < F2 < P + 2 (remember P + 2 is an upper bound on any earliest schedule). We distinguish three cases: the case where all the tasks are identical, the case where there is at least three types of tasks and the case where there is only two types of tasks. Figure 3 outlines the sub-cases that are successively addressed. 4.1 Identical tasks When all the tasks have a processing time equal to p and F1 or F2 is equal to kp, the schedule cannot complete at P (as in Theorem 3.1). In fact, we can even be more precise.

123

42

J.-C. Billaut, F. Sourd

1. Identical tasks 2. At least three different tasks 3. Two different tasks (a) One task has only one occurrence (b) Both tasks have at least two occurrences (p2 > p1 ) i. {F1 , F 2 } = {p1 , p 2 } or {F1 , F 2 } = {P − p2 , P − p1 } ii. p2 = 2p1 iii. p2 = kp1 (k > 1) iv. p2 is not a multiple of p1 .

Fig. 3 Outline of the proof

Lemma 4.1 In the problem with two distinct forbidden start times, when all the tasks are identical, i.e. if K = 2, 0 < F1 < F2 < P + 2 and pi = p ∀i, 1 ≤ i ≤ n, the optimal makespan is equal to: • • •

P if F1 = kp and F2 = k  p for all k, k  , 0 ≤ k ≤ k  < n; P + 2 if {F1 , F2 } = {kp, k  p + 1} for some k, k  , 0 ≤ k ≤ k  < n; P + 1 otherwise.

Proof The makespan is either P, P + 1 or P + 2. Since all the tasks are identical, all the task sequences are equivalent. The makespan is equal to P if and only if the kth task in the sequence starts at (k − 1) p. Such a schedule is feasible if and only if F1 = kp and F2 = k  p for all k, k  , 0 ≤ k ≤ k  < n. If this condition is not satisfied, the schedule is at least P + 1. Let us consider the smallest k such that kp is forbidden. If kp = F2 , we have a schedule of length P + 1. If kp = F1 , we conclude the proof by using Theorem 3.1. 

Since there is only one machine and only one type of tasks, the optimal makespan value is known in constant time. 4.2 At least three different tasks Lemma 4.2 If there are three different tasks, we can build an optimal schedule with a makespan equal to P. Proof We can assume without loss of generality that p1 > p2 > p3 and p1 ≥ p j for j ∈ J . We first schedule the tasks J4 , J5 , . . . , Jn until we cannot add a task that completes strictly before F1 . Let t be the completion time of the last scheduled task. Let us first consider the four following sub-cases. •

•

F1 − t ≤ p3 : As the three tasks J1 , J2 and J3 have different processing times, there is at least one task J j among J1 , J2 , J3 such that t + p j ∈ {F1 , F2 }. Once we have scheduled J j , we have to schedule the remaining tasks after t + p j . As F1 < t + p j , there is at most one forbidden start time and at least two different tasks, which means, according to Theorem 3.1, that we can schedule all the tasks without idle time and the schedule completes at P. / F or t + p2 ∈ / F, we can schedule J1 or J2 so that, p3 < F1 − t ≤ p2 : If t + p1 ∈ as in the previous case, the remaining problem has at least two different tasks and

123

Single machine scheduling with forbidden start times

•

43

one forbidden start time. Otherwise F1 = t + p2 and F2 = t + p1 . We can then start J3 at t and J1 at t + p3 . J1 completes after F2 so that the remaining tasks can be scheduled in any order. / {2, 3} verifies F1 − t ≤ p j ≤ p1 . p2 < F1 − t: Any unscheduled task J j with j ∈ – If there exists at least one unscheduled task J j with j ≥ 4, we can start at t either J1 alone, or J2 + J1 , or J3 + J1 . At least one of these possibilities do not meet any forbidden start time because t + p3 < t + p2 < F1 and there are three possible different completion times for J1 . After the completion of J1 , we have again at most one forbidden start time and at least two different tasks (since J j is unscheduled). – Otherwise, all the tasks J4 , . . . , Jn are scheduled before t. If we start J3 at t, it completes at t + p3 < F1 . If there is no idle time, the completion time of the last job must be either P − p1 or P − p2 . Therefore a feasible schedule can be built unless F = {P − p1 , P − p2 }. Conversely, if F = {P − p1 , P − p2 }, we can schedule J3 so that is completes at P because P − p3 > F2 = P − p2 . We can also start J2 at t because t + p2 = P − p1 − p3 < P − p1 = F1 . Therefore a feasible schedule can be built again. 

4.3 Two types of tasks From now on, we consider that there are two distinct subsets of tasks. The first one contains k1 tasks (k1 > 0) with processing time p1 and the second one contains k2 tasks (k2 > 0, k1 + k2 = n) with processing time p2 . In this problem, tasks with identical settings are to be processed several times: we are therefore in the field of high multiplicity scheduling et al. 2005). We observe that the problem can be
(Brauner 2 log ki + log pi ) space, which means that the number compactly encoded in O( i=1 of tasks is exponential in the size of the input of the problem. Abusing notation, we will denote by Ji any task with length pi (for i ∈ {1, 2}). In other words, we have k1 occurrences of task J1 and k2 occurrences of task J2 . 4.3.1 First case: k1 = 1 We first consider the case where k1 = 1 and k2 = n − 1. Since there is no assumption on the processing times p1 and p2 , the case “k1 = n − 1 and k2 = 1” is identical. If F1 > k2 p2 = (n − 1) p2 , then a schedule that first sequences the k2 tasks J2 followed by task J1 (that starts at (n − 1) p2 ) does not meet any forbidden start time, completes at P and is optimal. In the following we assume that F1 ≤ (n − 1) p2 . Lemma 4.3 It is assumed that k1 = 1 and F1 ≤ (n − 1) p2 . There is an optimal schedule where J1 does not start before t = F1p−1 p2 . Moreover, the optimal make2 span is given by 1. 2. 3.

Suppose {t + p1 , t + p2 } = {F1 , F2 }, then the optimal makespan is P + 1. Suppose F1 = t + p2 . If furthermore F2 ≥ t + p1 and P − F2 = kp2 then the optimal makespan is P + 1, otherwise, it is P. Otherwise, the optimal schedule is P.

123

44

J.-C. Billaut, F. Sourd

Proof We first prove the initial statement of the lemma about the start time of J1 . As F1 ≥ 0, we have t ≥ 0. Moreover, we have by construction that t < F1 ≤ t + p2 . If J1 starts before  t, it  starts at time λp2 where λ is the number of tasks J2 before J1 . F1 −1 We have λ < ≤ k2 . If we swap J1 with its successor (a task J2 ), task J1 can p2 start at (λ + 1) p2 ≤ t < F1 without violating any forbidden start time. We iterate this swap operation until J1 starts at t. Let us now compute the optimal makespan in each of the three sub-cases. 1.

2.

3.

Let us assume {t + p1 , t + p2 } = {F1 , F2 }. In the optimal schedule that contains only tasks J2 before t, we have either an idle slot at t, or a task is started and followed by an idle slot. It means that there is no optimal schedule that complete at P and P + 1 is a lower bound. Such a makespan is reachable if we start the longest task (among J1 or J2 ) at t + 1. It completes at F2 + 1, which means that all the remaining tasks can be scheduled in any order before P + 1. If J2 was scheduled at t or if a time slot was inserted, the makespan would be at least P + 1. We show that by scheduling J1 , we have a makespan at most P + 1 (which means that scheduling J1 at t is the optimal decision). Since t + p1 = F1 and t + p1 = F2 (otherwise, we would be in the first case), we can start a task J2 at t + p1 . As F1 < t + p1 + p2 , any resulting schedule contains at most one idle slot due to F2 . The optimal schedule is given by optimally scheduling the remaining task J1 subject to an eventual forbidden start time, which is done following Theorem 3.1. Rewriting the conditions of the theorem in the present case gives that the makespan is equal to P + 1 if F2 ≥ t + p1 and P − F2 is a multiple of p2 . Otherwise, the makespan is P. We have t + p2 = F1 . If t + p2 = F2 (then t + p1 = F1 , otherwise it would be the first case), we can schedule J1 at t and J2 between t + p1 and t + p1 + p2 > F2 , which means that the remaining tasks can be scheduled without idle time. If t + p2 = F2 , we can schedule a task J2 at t. By definition of t, it completes after F1 , which means that two different tasks must be scheduled after t + p2 subject to at most one forbidden start time. It can be done without idle time according to Theorem 3.1. 

4.3.2 Second case: k1 > 1 We now study the case where k1 ≥ 2 and k2 ≥ 2. Without loss of generality, we can assume that p1 < p2 . We first consider two special cases where the schedule cannot complete at P. Afterwards, we will show that in any other case a schedule completing at P exists. Lemma 4.4 If {F1 , F2 } = { p1 , p2 } or {F1 , F2 } = {P − p2 , P − p1 }, then the minimum makespan is equal to P + 1. Proof We only prove the results when {F1 , F2 } = { p1 , p2 }, the other case is symmetric. Any schedule must start by either a task J1 or a task J2 . Whatever the first task is, the second task cannot start at the completion of its predecessor. Therefore the makespan is at least P + 1. Such a makespan can be reached by first scheduling a task 

J2 followed by the other tasks in any order.

123

Single machine scheduling with forbidden start times

45

J2 0

p1

p1 + p2

p1 + 2p2

F1

J2 F2

P

Fig. 4 Illustration of the proof of Lemma 4.6

Lemma 4.5 Let us assume we have p2 = 2 p1 . If {F1 , F2 } = {(k − 1) p1 , kp1 } for some k < k1 + 2k2 , the minimum makespan is equal to P + 1. Otherwise, it is equal to P. Proof Let us first assume that F1 = (k −1) p1 and F2 = kp1 . Whatever is the schedule before F1 , if there is no inserted idle time we have either a task that completes at F1 or a task that completes at F1 − p1 since p2 = 2 p1 . In the first case, an idle slot is necessary at time F1 . In the second case, an idle slot is necessary at time F1 if we schedule a task J1 or at time F2 is we schedule a task J2 . Therefore the makespan is at least P + 1. Conversely, a schedule with makespan P + 1 exists: we first schedule a task J2 starting at F1 − p1 and completing at F2 . We can fill the time interval [0, F1 − p1 ) with tasks such that there is no more idle time and compute all the remaining tasks after F2 + 1. The schedule has only one idle slot, its makespan is equal to P + 1. Consider now that {F1 , F2 } = {(k − 1) p1 , kp1 }. If both F1 and F2 are not multiple of p1 any sequence is feasible and completes at P. We consider now three sub-cases. • • •

F1 = λp1 and F2 is not multiple of p1 : we just have to schedule one task J2 at time F1 − p1 and the optimal makespan is equal to P. F2 = λ p1 and F1 is not a multiple of p1 : this case is similar to the previous one. F1 = λp1 and F2 = λ p1 with λ ≥ λ + 2: we can schedule two tasks J2 at times F1 − p1 and F2 − p1 (they do not collapse). As there are at least two tasks J1 , the schedule can be filled without idle time and the makespan is P. 

We now show that in any other case, we can find a schedule with a makespan equal to P. We consider two cases, where p2 = kp1 (Lemma 4.6) or not (Lemma 4.7). Lemma 4.6 If k1 ≥ 2 and k2 ≥ 2, {F1 , F2 } = { p1 , p2 }, {F1 , F2 } = {P − p2 , P − p1 } and p2 = kp1 (for some integer k greater than 2), then there exists a schedule of makespan P. Proof We consider all the schedules with no idle time and we show that at least one schedule has no task starting at time F1 or F2 . If F1 = λp1 (for all λ), then any such schedule avoids F1 and, according to Theorem 3.1, there exists a schedule with makespan P. We have a similar conclusion if F2 = λp1 (for all λ). Therefore we consider that F1 = λ1 p1 and F2 = λ2 p1 . Figure 4 illustrates an instance with k = 3, λ1 = 11 and λ2 = 15. Let us first assume that F1 < p2 . If F2 = p2 , we can schedule a task J2 between 0 and p2 . The k1 tasks J1 and k2 − 1 > 0 tasks J2 are to be scheduled without idle time after p2 subject to the forbidden start time F2 , which is feasible according to Theorem 3.1. If F2 = p2 , we have F1 = p1 by hypotheses and we can schedule a task J1 between 0 and p1 and a task J2 between p1 and p1 + p2 . Since F2 = p2 is the latter forbidden start time, p1 + p2 is not forbidden and all the remaining tasks can

123

46

J.-C. Billaut, F. Sourd

be scheduled in any order and no idle time has been inserted. If F2 > P − p2 , we can symmetrically build a schedule that completes at P. We now consider the remaining case, that is p2 ≤ F1 ≤ F2 ≤ P − p2 . Let f 1 (resp. f 2 ) be the remainder of λ1 (resp. λ2 ) when divided by k. The set {0, 1, 2}−{ f 1 , f 2 } contains at least one element. Let x be such an element. In Fig. 4, f 1 = 2 and f 2 = 0 which means that x must be equal to 1. We consider the slots corresponding to the intervals [p1 , ( + 1) p1 ] and the superslots corresponding to [x p1 + p2 , x p1 + ( + 1) p2 ]. By construction, no superslot starts at a forbidden start time, there is no forbidden start time neither before the first superslot in [0, x p1 ] nor after the last superslot in [x p1 + yp2 , P] with y = (P − x p1 )/ p2 . To build a schedule without idle slot, we schedule x tasks J1 before x p1 . Then, we place a task J2 in the superslots that contain F1 and F2 (F1 and F2 may be in the same superslot or in two different superslot). Then, we place the remaining tasks J2 in the superslots that completes before P. Finally, we place the remaining tasks J1 in the remaining slots. 

Lemma 4.7 If k1 ≥ 2 and k2 ≥ 2, {F1 , F2 } = { p1 , p2 }, {F1 , F2 } = {P − p2 , P − p1 } and p2 / p1 not integer ( p1 < p2 ), the schedule can be completed at P. Proof We first build the following pseudo-schedule (that may violate one or both forbidden start times): all the k2 tasks J2 are scheduled without idle time between 0 and k2 p2 then all the k1 tasks J1 are scheduled between k2 p2 and P. Then, we show that this schedule can be repaired to become feasible. Clearly, if it does not violate any forbidden start time, no reparation is required. •

Let us assume that a task J2 completes at some forbidden start time F ∈ {F1 , F2 } (let J denote this occurrence of task J2 ). We then modify the schedule by moving the last task to the first position (the tasks are scheduled from 0 to P, forbidden start times are still ignored). As p1 < p2 , the forbidden start time F is strictly between the start and the end time of J and therefore it is not violated. Let us consider the second forbidden start time F  ∈ {F1 , F2 }\{F}. If no task starts at time F  , the schedule is optimal. Otherwise, let J  be the task that completes at F . – If J  is the first task of the schedule, we swap the first two tasks. Since F  = p1 , we have F = p2 by hypotheses so that the swap operation repairs the violations of F  without violating F. The schedule is feasible and of length P. – If J  is a task J2 , we move again the last task (a task J1 as k1 ≥ 2) to the first position. F  is now between the end and start time of J  . We can also prove that no task starts at F: otherwise, we would have 2 p1 = kp2 for some integer k. As p2 > p1 , we would have p2 = 2 p1 , which is impossible. Therefore the schedule is feasible and of length P. – If J  is a task J1 and is not the first task, F  = k2 p2 + λp1 for some λ such that 1 < λ < k1 . We move the last task J2 to the last position. The completion time of the tasks J1 are now of the form (k2 − 1) p2 + λ p1 = F  − p2 + (λ − λ ) p1 . Since p2 is not a multiple of p1 , F  is not a completion time of any task J1 . A task J1 can complete at F only if F = k2 p2 but it would also mean that p2 is a multiple of p1 . Therefore, the schedule is feasible.

123

Single machine scheduling with forbidden start times

•

47

We have proved that if a task J2 completes at F then the schedule is feasible and of length P. Let us now assume that some task J1 completes at F = k2 p2 +λp1 (and F  = kp2 for all k ∈ {1, . . . , k2 }). If there are two such tasks, we consider the latest one. As F < P, we have λ < k1 . We now build a modified schedule by sequencing k2 − 1 tasks J2 , λ + 1 tasks J1 , the last task J2 and all the other tasks J1 . F is between the start and end times of the last task J2 . Only the λ first tasks J1 and the last task J2 have moved. Therefore, if there is a violation of the second start time F  , we have F  = (k2 − 1) p2 + kp1 for some k ∈ {1, . . . , λ + 1}. If k ≤ λ then, there is only one forbidden start time before (k2 − 1) p2 + (k + 1) p1 and two different tasks. So Theorem 3.1 shows that the tasks can be resequenced so that there is no violation. If k = λ + 1, then F  is equal to the start time of the last task J2 . By construction, this task cannot be the last one (otherwise we would have {F1 , F2 } = {P − p1 , P − p2 } and we can swap it with its successor (denoted by J  ). J  starts at F  but does not complete at F (otherwise, we would have p2 = 2 p1 ). We can then move the first task J2 and reinsert it just after J  : now F  is between the start and the end of this task J2 and there is no more violation. 

4.4 Complexity In this section, we have considered all the possible cases that may happen when there are two distinct forbidden start times. For each case, we presented how to build an optimal schedule. For a given instance, we can check in O(n) time to which case (according to Fig. 3) the instance belongs. Then, for any case, we can build the schedule in O(n) time. Therefore, we have the following theorem. / F, K ≤ 2|Cmax can be solved in O(n) time. Theorem 4.1 1|S j ∈ 5 Small number of forbidden start times We have proved that our scheduling problem with forbidden start times is polynomial when the number K of forbidden start times is equal to 1 or 2 but it is N P-complete for arbitrary values of K . We complete this study by proving that the problem is polynomial when K is considered as a constant that is we propose an optimal algorithm that runs in O(n p(K ) ) with p(K ) a (polynomial) function of K . Since p(K ) quickly grows with K , this algorithm is only tractable for small values of K . The precise study of the previous section shows that a large number of sub-cases are to be considered when K = 2. It seems hard to generalize such a study for K = 3 or for a general value of K . Therefore, our approach here is different and based on dynamic programming. However, we do not study the complexity of compactly encoded instances as in Sect. 4.3. First, we give in Lemma 5.2 a counterpart of Lemma 4.2 that shows that instances with a large number of different jobs are easy. This result is the key for polynomially bounding the number of states in the dynamic programming. We recall that the

123

48

J.-C. Billaut, F. Sourd

forbidden start times are numbered such that 0 < F1 < · · · < FK < P + K . The following lemma and its corollary isolate the transformation used to prove Lemma 5.2. We define an active pseudo-schedule as a schedule without idle time that may violate the forbidden start times, i.e. a potentially non-feasible schedule without idle time. Job J j starting at time t is said to be a straddling job if there exists a forbidden start time Fk such that t < Fk ≤ t + p j . Lemma 5.1 Let us consider an instance where the tasks are pairwise different, that is their processing times are different. If there exists an active pseudo-schedule in which the last 2K − 1 tasks are non-straddling then there exists a schedule that completes at P. Proof (by induction) From the previous section, the lemma is true for K = 1 or K = 2. We assume that the lemma is true for all K  < K . Let S be the set of the last 2K − 1 non-straddling tasks. If the pseudo-schedule is feasible, there is nothing to prove. Conversely, let J j be the first task in the schedule that completes at a forbidden start time. Let t be the start time of J j . Since t + p j is forbidden and the processing times of the tasks in S are different from p j , there is at least one task—say Ji1 —in S such that t + pi1 is not forbidden. We schedule Ji1 at t, that is we move it and reinsert it before J j . If t + pi1 + p j is not forbidden, we let J j start at t + pi1 . Otherwise, we have to find By a second job Ji2 in S to be inserted before J j such that t + pi1 + pi2 is not
forbidden. x pik )+ p j this way, we iteratively schedule x jobs Ji1 , Ji2 , . . . , Ji x of S until t +( k=1
x−1 is not forbidden. We have x ≤ K since t + p j , t + pi1 + p j , . . . , t + ( k=1 pik ) + p j are x distinct forbidden start times. Therefore, at step l of the above algorithm (for any l ≤ x), there remain 2K − 1 − (l − 1) = 2K − l ≥ K non-straddling tasks in S
so that we are able to find Jil in S such that its completion time t + lk=1 pik is not a forbidden start time. In the new schedule, there are at least x forbidden start times but no violation before the completion of J j . Let us consider the tasks scheduled after J j : we have a subproblem with at most K − x forbidden start times and the last 2K − 1 − x tasks are non-straddling. By induction, since 2K − 1 − x > 2(K − x) − 1, we are able to build a feasible schedule. 

Corollary 5.1 Let us consider an instance where the tasks are pairwise different, that is their processing times are different. If there exists an active pseudo-schedule in which there is a subsequence of 2K − 1 adjacent non-straddling tasks, then there exists an active feasible schedule. Proof Let K  be the number of straddling tasks before this subsequence. From Lemma 5.1, we can repair the part of the pseudo-schedule before the subsequence such that no task starts at a forbidden start time. In the new schedule, we still have a subsequence of 2K − 1 − K  ≥ 2(K − K  ) − 1 tasks. We can then similarly repair the part of the pseudo-schedule before the subsequence by applying Lemma 5.1 with the time reversed. 

Lemma 5.2 If there are at least L = 2K (K + 1) different tasks, we can build an optimal schedule with a makespan equal to P.

123

Single machine scheduling with forbidden start times

49

Proof (by induction) Let J  be the maximal subset of J such that J  does not contain two jobs with the same processing time. In other words, J  contains one occurrence of each job in J so, from the statement of the lemma, we have |J  | ≥ L. We first schedule, by list scheduling, the jobs of J − J  until we are not able to schedule a job strictly before F1 . Let t be the completion time of the last scheduled task. We have t < F1 and we consider the two following cases: •

•

If F1 − t > pmax = max j∈J p j , it means that all the jobs in J − J  are scheduled before F1 . Therefore we have to schedule the tasks of J  in the time interval [t, P] without idle time. All the tasks are pairwise different. We only consider this subproblem and forget the tasks scheduled before t. We first build a pseudo-schedule by ignoring the forbidden start times. There are at most K straddling tasks. We consider the longest subsequence of non-straddling tasks between two straddling tasks. There are at most K + 1 such subsequences and, since there are at least 2K (K + 1) tasks, the longest subsequence contains at least 2K − 1 tasks. By Corollary 5.1, we can repair the pseudo-schedule to make it feasible. Otherwise (that is F1 − t ≤ pmax ), there are at least L different unscheduled tasks. We first try to schedule one task in C = {J j | p j > F1 − t} such that it does not complete at a forbidden start time. If |C| ≥ K + 1, such a task exists. Otherwise (that is |C| ≤ K ), there are at least L − K > K tasks with a processing time less than F1 − t. So there exists some job J j such that t + p j < F1 and / F. In both cases, we are able to build a partial schedule that t + p j + pmax ∈ completes after F1 and does not violate any forbidden start time. Moreover there are at least L − 2 > 2(K − 1)K different unscheduled tasks and at most K − 1 forbidden start times after t + p j + pmax . Therefore, by induction, we are able to build a feasible schedule. 

According to the previous lemma, we only have to solve the case where there are at most M = L − 1 different types of tasks. Similarly to Sect. 4.3, we will say that the instances contain k1 jobs J1 , k2 jobs J2 … and k M jobs J M . For the dynamic programming algorithm, we define the boolean values P(i 1 , i 2 , . . . , i M , k) that are true if and only if we can schedule i 1 jobs J1 , i 2 jobs
J2 … and i M jobs J M in the time interval [0, T ] with T = T (i 1 , . . . , i M , k) = k + M j=1 i j p j . In other words, k is the number of allowed idle slots. In an optimal schedule for this problem, we either have that the time slot [T − 1, T ] is idle or that some job J j completes at T , which means that its start time T − p j does not belong to F. In the first case, P(i 1 , i 2 , . . . , i M , k) is true if and only if P(i 1 , i 2 , . . . , i M , k − 1) is true. In the second case, P(i 1 , i 2 , . . . , i M , k) is true if and only if P(i 1 , . . . , i j − 1, . . . , i M , k) is true. Therefore we have P(i 1 , i 2 , . . . , i M , k) = P(i 1 , i 2 , . . . , i M , k − 1) ⎛ ⎞  ∨⎝ P(i 1 , . . . , i j − 1, . . . , i M , k)⎠ j|T − p j ∈ /F


with T = T (i 1 , . . . , i M , k) = k + M j=1 i j p j . The minimal makespan for the problem is given by P + k  where k  is the smallest integer such that P(k1 , k2 , . . . , k M , k  )

123

50

J.-C. Billaut, F. Sourd

is true. Assuming that we have pre-sorted the elements of F in an array and the processing times p1 , . . . , p M in a second array, each value P(i 1 , i 2 , . . . , i M , k) can be computed in O(K + M), that is in O(K 2 ). Therefore, the time complexity of the

3 2K 2 +2K −1 ). dynamic programming algorithm is in O(K 3 M j=1 k j ), that is O(K n The space complexity is in O(K n 2K +2K −1 ). The algorithm is then polynomial when K is assumed to be a constant. We observe that in the case with K = 2 forbidden start times, Lemma 4.2 shows that we can take L = 3 so that the dynamic programming approach leads to an O(n 2 ) algorithm, whereas Sect. 4 is devoted to an O(n) algorithm. 2

6 Conclusion We have considered in this paper a new scheduling problem, assuming that some starting times are forbidden. For the single machine problem and makespan minimization we have shown that the general problem is strongly N P-hard. Assuming that only one or two starting times are forbidden, we show that the problem can be solved in linear time. When the number of forbidden start times is seen as a constant, the problem remains polynomial. In order to improve the complexity of the dynamic programming algorithm of Sect. 5, we can search for a smaller L in Lemma 5.2. Clearly, L must be greater than K but we conjecture that the lemma holds for L = K + 1. This study is devoted to the makespan. Further works could consider the sum of (weighted) completion times since this problem is polynomial when there is no forbidden start time. In an environment with several machines, several variants of the forbidden start times can be imagined. An interesting one would be to allow at most one task to start at any time point. References Brauner N, Crama Y, Grigoriev A, van de Klundert J (2005) A framework for the complexity of highmultiplicity scheduling problems. J Comb Optim 9:313–323 Garey MR, Johnson DS (1979) Computers and intractability; a guide to the theory of N P-completeness. W.H. Freeman, New York Gharbi A, Haouari M (2005) Optimal parallel machines scheduling with availability constraints. Discrete App Math 148(1):63–87 ILOG Inc (2003) ILOG Scheduler Reference Manual. October Keil J (1992) On the complexity of scheduling tasks with discrete starting times. Oper Res Lett 12(5):293– 295 Lee C-Y (1996) Machine scheduling with an availability constraint. J Glob Optim 9(3–4):395–416 Lee C-Y (1999) Two-machine flowshop scheduling with availability constraints. Eur J Oper Res 114(2):420–429 Lee C-Y (2004) Machine scheduling with availability constraints. In: Leung JYT (ed) Handbook of scheduling: algorithms, models and performance analysis, Chap 22. Chapman & Hall/CRC, Boca Raton Ph Mauguière, Billaut J-C, Bouquard J-L (2005) New single machine and job-shop scheduling problems with availability constraints. J Sched 8:211–231 Nakajima K, Hakimi SL (1982) Complexity results for scheduling tasks with discrete starting times. J Algor 3(4):344–361 Rosenkrantz DJ, Yu L, Ravi SS (2001) Efficient construction of minimum makespan schedules for tasks with a fixed number of distinct execution times. Algorithmica 3(1):83–100

123