Single Machine Inserted Idle Time Scheduling with Release Times and Due Dates Natalia Grigoreva Department of Mathematics and Mechanics, St.Petersburg State University, Russia n.s.grig@gmail.com Abstract. The single machine scheduling problem is considered in which each task has a release dates, a processing time and a due date. The objective is to mimimize the maximum lateness. Preemption is not allowed. Scheduling prob- lem 1|rj |Lmax is a NP-hard problem. We define an IIT (inserted idle time) schedule as a feasible schedule in which a processor is kept idle at a time when it could begin processing an operation. We propose an approximate IIT algo- rithm named ELS/IIT (earliest latest start/ inserted idle time) and branch and bound algorithm, which produces a feasible IIT schedule for a fixed the max- imum lateness L. In order to optimize over L we must iterate the scheduling process over possible values of L. New dominance criteria are introduced to cur- tail the enumeration tree. By this approach it is generally possible to eliminate most of the useless nodes generated at the lowest levels of decision tree. 1 Introduction The problem of minimizing the maximum lateness while scheduling tasks to single processor is a classical combinatorial optimization problem. Following the 3-field clas- sification scheme proposed by Graham et al. [1], this problem is denoted by 1|rj |Lmax . This problem relates to the scheduling problem [2], it has many applications, and it is N P -hard [3]. The approximation algorithms for single processor scheduling problem were given by Potts[4], Hall and Shmoys [5]. This algorithms used extended Jackson’s rule with some modifications. The problem is solved by the extended Jackson’s rule: whenever the machine is free and one or more tasks available for processing, schedule an available task with earliest due data. This algorithms construct an nondelay schedule. A nondelay schedule has been defined by Baker[6] as a feasible schedule in which no processor is kept idle at a time when it could begin processing a task. An inserted idle time schedule (IIT) has been defined by J.Kanet and V.Sridharam [7] as a feasible schedule in which a processor is kept idle at a time when it could begin processing a task. J.Kanet and V.Sridharam [7] reviewed the literature with problem setting where IIT scheduling may be required. In [8] we considered scheduling with inserted idle time for m parallel identical processors and proposed branch and bound algorithm for multiprocessor scheduling problem with precedence-constrained tasks. In [9] we proposed the approximation IIT Copyright ⃝ c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org Single Machine Inserted Idle Time Scheduling 337 algorithm for P |rj |Lmax problem. The goal of this paper is to propose IIT schedule for 1|rj |Lmax problem. We propose an approximate IIT algorithm named ELS/IIT (earli- est latest start/ inserted idle time) and branch and bound algorithm, which produces a feasible IIT(inserted idle time) schedule for a fixed maximum lateness L. The algo- rithm may be used in a binary search mode to find the smallest maximum lateness. A new method for evaluating partial solutions, selecting the next task and new ways of reducing the exhaustive search was designed. We consider a system of tasks U = {u1 u2 , . . . , un }. Each task is characterized by its execution time t(ui ), its release time r(ui ) and its due dates D(ui ). Release time r(ui ) is the time at which the task is ready for processing. Due date D(ui ) specifies the time limit by which the task should be completed. Set of tasks is performed on one processor. Task preemption is not allowed. A schedule for a task set U is the mapping of each task ui ∈ U to a start time τ (ui ). Maximum lateness of schedule S is the quantity Lmax = max{τ (ui ) + t(ui ) − D(ui )|ui ∈ U }. First, we propose an approximate IIT algorithm named ELS/IIT (earliest latest start/ inserted idle time). Then by combining the ELS/IIT algorithm and B&B method this paper presents BB/IIT algorithm which can find optimal solutions for single pro- cessor scheduling problem. 2 Approximate algorithm ELS/IIT For each task ui , we know the earliest starting time r(ui ) and the latest start time vmax (ui ) = D(ui ) − t(ui ), which is a priority of task. Let k tasks have been put in the schedule and partial schedule Sk have been constructed. Let be tmin (k) the time of the termination of the processor after completion all tasks from the partial schedule Sk . The approximate schedule is constructed by ELS/IIT algorithm as follows: 1. Select the task u0 , such as vmax (u0 ) = min{vmax (ui )|ui ∈ / Sk }. 2. If idle(u0 ) = r(u0 )−tmin (k) > 0 then choose a task u∗ ∈/ Sk , which can be executed during the idle time of the processor without increasing the start time of the task u0 . Namely define the start time of task ui as τ (ui ) = max{tmin (k), r(ui )} then set d(ui ) = τ (ui ) + t(ui ) and find task u∗ such as vmax (u∗ ) = min{vmax (ui )|d(ui ) ≤ r(u0 ), ui ∈ / Sk }. 3. If the task u∗ is found, then we assign to the processor the task u∗ , otherwise the task u0 . Suppose that Lopt denotes the maximum lateness of optimal schedule, while LELS denotes the the maximum lateness when the tasks are sequenced using ELS/IIT heuris- tic. We are interested in seeing how much worse LELS can be compared ∑n to Lopt . In what follows we will prove the following worse-case bound. Let T = k=1 t(k) and tmin = min{t(ui )|ui ∈ U }. 338 Natalia Grigoreva Lemma 1. LELS − Lopt tmin ≤1− . Lopt + Dmax T Proof. Suppose that the sequence π = (l1 , l2 , ..., ln ) is generated using ELS/IIT algo- rithm. In schedule π let task lj be the task with maximum lateness, then LELS = τ (lj )+ ∑j t(lj ) − D(lj ). Then we can find the task li such as LELS = r(li ) + k=i t(lk ) − D(lj ), where 1 ≤ li ≤ lj ≤ ln . If there is a choice, it is assumed that lj is as small as possible and that li is as large as possible. Then either task li is the first task in the schedule or the processor will be idle before the beginning of task li . Consider tasks from li to lj in the sequence π. If for all i ≤ k ≤ j − 1 it is true that D(lk ) − t(lk ) ≤ D(lk+1 ) − t(lk+1 ) then D(li ) − t(li ) ≤ D(lj ) − t(lj ). Otherwise we can find k such as i ≤ k ≤ j − 1 and task lk such as D(lk ) − t(lk ) > D(lk+1 ) − t(lk+1 ). But for k + 1 ≤ u ≤ j − 1 we have that D(lu ) − t(lu ) ≤ D(lu+1 ) − t(lu+1 ). Then τ (lk ) < r(lk+1 ) and τ (lk ) + t(lk ) ≤ r(lk+1 ). Hence during the application of ELS/IIT algorithm task lk+1 begins at its release date τ (lk+1 ) = r(lk+1 ), which contradicts the choice of task li . If k = j − 1 and task lj begins at its release date τ (lj ) = r(lj ) then schedule π is optimal schedule. In either case we have from the construction of schedule that D(li ) − t(li ) ≤ D(lj ) − t(lj ). On the other hand Lopt ≥ r(li ) + t(li ) − D(li ) ≥ r(li ) + t(lj ) − D(lj ) and Lopt ≥ T − Dmax . Then ∑ j ∑ j−1 LELS − Lopt ≤ r(li ) + t(lk ) − D(lj ) − r(li ) − t(lj ) + D(lj ) = t(lk ). k=i k=i Then ∑j−1 LELS − Lopt k=i t(lk ) tmin ≤ ≤1− . Lopt T T Single Machine Inserted Idle Time Scheduling 339 To illustrate ELS heuristic we consider the following example. There are two task: r1 = 0; t1 = T − 1; D1 = T − 1; r2 = 0; t2 = 1; D2 = 1 + δ. Then ELS/IIT algorithm will schedule the large task first and maximum lateness LELS = T − 1 − δ. But maximum lateness of optimal schedule Lopt = 1. This problem can be solved using extended Jackon’s rule (EDD): whenever the machine is free and one or more tasks are available for processing, schedule an available task with earliest due date. We consider examples, in which EDD algorithm builds a bad schedule, while ELS algorithm builds the optimal schedule and vice versa. For this example extended Jackson’s rule (EDD heuristic) makes the optimal schedule. But if we change example: r1 = 0; t1 = T − 1; D1 = T ; r2 = r; t2 = 1; D2 = 1, EDD heuristic will schedule the large task first and maximum lateness LEDD = T − 1. ELS/IIT algorithm generates optimal schedule LELS = r and Lopt = r; The example 2 from [5] in table 1 demonstrates the worse-case instance for ap- proximation algorithm B,which was proposed in [5]. There are five tasks, ri ,ti ,Di rep- resent the release date, processing time and due date, respectively, of task i. Li = τi + ti − Di and vmax (i) = Di − ti . ELS/IIT algorithm generates the optimal schedule Table 1. Example 2 Task ri ti Di vmax (i) τi Li (ELS) 1 0 Q 2Q + 2 Q + 2 Q + 2 0 2 1 Q 1 1−Q 1 Q 3 Q+1 1 0 -1 1+Q Q+2 4 2Q + 1 Q 2Q + 1 Q + 1 Q + 3 Q + 2 5 2Q + 2 1 Q+1 Q 2Q + 2 Q + 2 (2, 3, 1, 5, 4) with the maximum lateness LELS = Q + 2. Algorithm B [5] generates schedule (1, 2, 3, 4, 5) with the maximum lateness LB = 2Q + 2. 3 Algorithm for constructing an optimal schedule The branch and bound algorithm produces a feasible IIT schedule for a fixed maximum lateness L. In order to optimize over L we must iterate the scheduling process over possible values of L. Let Lopt be maximum lateness of optimal schedule. We defile interval (a, b] such as a < Lopt ≤ b. First we define the low bound of maximum lateness. We calculate two low bounds LB1 = max{r(ui ) + t(ui ) − D(ui )|ui ∈ U } and ∑n LB2 = max{ t(ui ) − Dmax }. i=1 340 Natalia Grigoreva Then the low bound of maximum lateness LB is LB = max{LB1, LB2}. ∑n The upper bound b = i=1 t(ui ) + rmax − Dmin [10]. Then Lopt ∈ (a, b]. Select z = ⌈(a + b)/2⌉ and use branch and bound method for constructing a feasible schedule BB(U, D + z; S). If we find a feasible schedule then we take interval (a, z], else we take interval (z, b] and repeat . Algorithm SCHEDU LE(U ; Sopt , Lopt ) 1. Calculate a b. 2. While b − a > eps do 3. Set z := ⌈(a + b)/2⌉. 4. We recalculate due dates D(ui ) as D∗ (ui ) = D(ui ) + z, recalculate makespan Dmax = max{D∗ (ui )|ui ∈ U } and the latest start times vmax (ui ) = D∗ (ui ) − t(ui ). 5. Use procedure BB(U, D∗ ; S, LS ) for constructing a feasible schedule. 6. If we find feasible schedule S , then Srec := S; Lrec := LS and set b := LS , else set a := z. 7. endwhile 8. Sopt := Srec , and Lopt := Lrec . 4 Branch and bound method for constructing a feasible schedule BB(U, D ∗ ; S) The branch and bound algorithm produces a feasible IIT( inserted idle time) schedule for a fixed maximum lateness L. In order to optimize over L we must iterate the scheduling process over possible values of L. For the formal description of the branch and bound method we must give a definition of partial solutions. It is convenient to represent the schedule as a permutation of tasks. For each permutation of tasks π = (ui1 , ui2 , . . . , uin ), one can construct a schedule Sπ as follows: the task is assigned to the processor at the earliest possible time. Partial solution σk , where k the number of jobs will be regarded as a partial permutation σk = (ui1 , ui2 , . . . , uik ), which is determined partial schedule. Definition 1. The solution γn = (l1 , l2 , . . . , ln ) is called the extension of partial solu- tions σk = (q1 , q2 , . . . , qk ), if l1 = q1 , l2 = q2 , . . . , lk = qk . Definition 2. A partial solution σk is called a feasible if there exists an extension of σk , which is a feasible schedule. For each task ui , we know the earliest starting time r(ui ) and the latest start time vmax (ui ) = D(ui ) − t(ui ), In order to make the feasible schedule, it is necessary that each task ui ∈ U, the start time of its execution τ (ui ) satisfies the inequality r(ui ) ≤ τ (ui ) ≤ vmax (ui ). Single Machine Inserted Idle Time Scheduling 341 In order to describe the branch and bound method it is necessary to determine the set of tasks that we need to add to a partial solution, the order in which task will be chosen from this set and the rules that will be used for eliminating partial solutions. Let I be the total ∑n idle time of processor in the feasible schedule S of length Dmax , then I = Dmax − i=1 t(ui ). For a partial solution σk we know for task idle(ui )— idle time of processor before start the task ui . At each level k will be allocated a set of tasks Uk , which we call the the ready tasks. These are tasks that need to add to a partial solution σk−1 , so check all the possible continuation of the partial solutions. Definition 3. Task u ∈ / σk is called ∑ the ready task at the level k, if r(u) satisfies the inequality r(u) − tmin (k) ≤ I − u∈σk idle(ui ). The main way of reducing of the exhaustive search will be the earliest possible identification unfeasible solutions. Definition 4. Let the task ucr ∈ / σk is such as vmax (ucr ) = min{vmax (u)|u ∈ / σk }. The task ucr ∈ / σk is called the delayed task for σk , if vmax (ucr ) < tmin (k). Below we formulate and proof the rules of deleting unfeasible partial solutions. Lemma 2. Let delayed task ucr for a partial solution σk exists, then 1. The partial solution σk is unfeasible. 2. For any task u, such as max{tmin k − 1, r(u)} + t(u) > vmax (ucr ) a partial solution σk−1 ∪ u is unfeasible. 3. If max{tmin (k − 1), r(ucr )} + t(ucr ) > vmax (uk ) then the partial solution σk−1 is unfeasible. Proof. 1. This follows from definition the delayed task. 2. Let tmin (k) is the time of ending all tasks which are included in a partial solution σk If the task ucr is delayed task, then vmax (ucr ) < tmin (k). After cancelation of the last scheduled task uk , algorithm returns to the partial solution σk−1 . Processor ends all task at time tmin (k − 1). If we add a task u to the partial solution σk−1 on step k, we must assign the task ucr on the processor on step k + 1. Therefore should be performed max{tmin (k), r(u)} + t(u) ≤ vmax (ucr ). 3. Consider two cases. 3.1 vmax (uk ) ≤ vmax (ucr ). If the task ucr is delayed task, then vmax (ucr ) < tmin (k). After deleting the task uk , the task ucr is assigned to processor. Processor ends all it’s task at time tmin (k) = max{tmin (k − 1), r(ucr )} + t(ucr ). On lemma max{tmin (k − 1), r(ucr )} + t(ucr ) > vmax (uk ), then the task uk will be the delayed task for partial solution σk = σk−1 ∪ ucr . 3.2. If vmax (uk ) > vmax (ucr ) then the partial solution σk−1 ∪ ucr was tested early and it was unfeasible. For any solution σk−1 ∪ u task uk or task ucr will be delayed task. The partial solution σk = σk−1 ∪ u is unfeasible for all u, then the partial solution σk−1 is unfeasible. 342 Natalia Grigoreva Algorithm 1 BB/IIT algorithm 1: Set k := 1; tmin (0) := 0; σ0 = ∅; 2: while (k > 0) and (k < n + 1) do 3: Determine the task ucr such as vmax (ucr ) = min{vmax (u)|u ∈ / σk−1 }; 4: if vmax (ucr ) ≤ tmin (k) then 5: Compute EST = est(σk−1 ); 6: if EST ≤ 0 then 7: Select the task u0 , use ELS/IIT procedure 8: Set the task u0 on processor and create partial solution σk = σk−1 ∪ u0 9: else 10: Perform step back and create the partial schedule σk−1 11: else 12: Delete all unfeasible partial solution by using Lemma 2 13: end if 14: end if 15: end while 16: if k = 0, then 17: Maximum lateness of optimal schedule is greater then LS . 18: end if 19: if k = n, then 20: We find feasible schedule S = σn and its maximum lateness is equal LS 21: end if Another method for determining unfeasible partial solutions based on a compari- son of resource requirements of tasks and processor power. In this case we propose to modify the algorithm for determining the interval of concentration [11] for the com- plete schedule. We apply this algorithm to a partial schedule σk and determine its admissibility. We consider time intervals [t1 , t2 ] ⊆ [tmin (k), Dmax ]. For all tasks ui ∈ / σk we find minimal time of its begin: v(ui ) = max{r(ui ), timek }. Let L([t1 , t2 ]) be a length of time interval [t1 , t2 ]. Let Mk (t1 , t2 ) be the total minimal time of tasks in time interval [t1 , t2 ], then ∑ Mk (t1 , t2 ) = min{L(xk (ui )), L(y(ui ))}, ui ∈σ / k where xk (ui ) = [v(ui ), v(ui ) + t(ui )] ∩ [t1 , t2 ], y(ui ) = [vmax (ui ), vmax (ui ) + t(ui )] ∩ [t1 , t2 ]. Let est(σk ) = max {Mk (t1 , t2 ) − (t2 − t1 ).} [t1 ,t2 ]∈[tmin (k),Dmax ] Lemma 3. If est(σk ) > 0 then a partial solution σk is unfeasible. The pseudo-code of Branch and bound method for constructing a feasible schedule BB(U, D; S) is shown in Algorithm 1. Single Machine Inserted Idle Time Scheduling 343 5 Conclusions In this paper we propose IIT schedule for 1|rj |Lmax problem. We propose an ap- proximate IIT algorithm named ELS/IIT (earliest latest start/ inserted idle time) and branch and bound algorithm, which produces a feasible IIT(inserted idle time) schedule for a fixed maximum lateness L. The algorithm may be used in a binary search mode to find the smallest maximum lateness. We compare IIT algorithm and algorithms which use extended Jackson’s rule. We can see, that algorithms build good schedule for various examples, so combining the two approaches, we can get the best solutions for all examples. References 1. Graham R.L., Lawner E.L. and R. Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey // Ann. of Disc. Math. 1979. Vol. 5, 10. P. 287–326. 2. P. Brucker. Scheduling Algorithms, (1997). 3. Lenstra J.A.,R. Kan. and Brucker P. Complexity of machine scheduling problems//Ann. of Disc. Math. 1977, 1 P.343–362. 4. Potts C.N. Analysis of a heuristic for one machine sequencing with release dates and delivery times// Operational Research. 1980. V.28 No. 6, P. 445–462. 5. Hall L.A., Shmoys D.B. Jackson’s rule for single-mashine scheduling: making a good heuris- tic better// Mathematics of operations research. 1992. V.17., No.1. P 22–35. 6. K.R.Baker. Introduction to Sequencing. John Wiley & Son, New York(1974). 7. J. Kanet and V. Sridharan. Scheduling with inserted idle time:problem taxonomy and literature review, Oper.Res 48 (1), pp.99-110, (2000). 8. Grigoreva N.S. Branch and bound method for scheduling precedence constrained tasks on parallel identical processors // Lecture Notes in Engineering and Computer Science: Proc. of The World Congress on Engineering 2014, WCE 2014, 2–4 July, 2014, London, U.K., P. 832–836. 9. Grigoreva N.S. Multiprocessor Scheduling with Inserted Idle Time to Minimize the Max- imum Lateness// Proceedings of the 7th Multidisciplinary International Conference of Scheduling: Theory and Applications. Prague, MISTA. 2015, P. 814–816. 10. Mastrolilli M. Efficient approximation schemes for scheduling problems with release dates and delivery times//Journal of Scheduling.2003.6,P.521–531. 11. Fernandez E., Bussell B. Bounds the number of processors and time for multiprocessor optimal schedules //IEEE Trans. on Computers. 1973, Vol. 4, 11 P. 745–751.