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 problem 1jrjjLmax is a NP-hard problem. We de ne 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 algorithm named ELS/IIT (earliest latest start/ inserted idle time) and branch and bound algorithm, which produces a feasible IIT schedule for a xed the maximum 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 curtail 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.
Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. algorithm for P jrjjLmax problem. The goal of this paper is to propose IIT schedule for 1jrjjLmax problem. We propose an approximate 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 xed maximum lateness L. The algorithm may be used in a binary search mode to nd 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 = fu1u2; : : : ; ung. 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) speci es 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 2 U to a start time (ui). Maximum lateness of schedule S is the quantity
Lmax = maxf (ui) + t(ui)
D(ui)jui 2 U g:
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 nd optimal solutions for single processor scheduling problem. 2
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) = minfvmax(ui)jui 2= Skg: 2. If idle(u0) = r(u0) tmin(k) > 0 then choose a task u 2= Sk, which can be executed during the idle time of the processor without increasing the start time of the task u0.
Namely de ne the start time of task ui as (ui) = maxftmin(k); r(ui)g then set d(ui) = (ui) + t(ui) and nd task u such as vmax(u ) = minfvmax(ui)jd(ui) r(u0); ui 2= Skg: 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 heuristic. We are interested in seeing how much worse LELS can be compared to Lopt. In what follows we will prove the following worse-case bound. Let T = ∑kn=1 t(k) and tmin = minft(ui)jui 2 U g. then and
Lemma 1.
1 tmin :
T Proof. Suppose that the sequence = (l1; l2; :::; ln) is generated using ELS/IIT algorithm. In schedule let task lj be the task with maximum lateness, then LELS = (lj)+ t(lj) D(lj). Then we can nd the task li such as LELS = r(li) + ∑jk=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 rst 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
k j
But for k + 1 u j
D(lk) t(lk)
D(lk+1) t(lk+1) D(li) t(li)
D(lj) t(lj): D(lk) t(lk) > D(lk+1) t(lk+1): 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):
r(li) + t(li) D(li) r(li) + t(lj) D(lj)
T
j r(li) + ∑ t(lk) k=i j 1 D(lj) r(li) t(lj) + D(lj) = ∑ t(lk): k=i
∑jk=1i t(lk)
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 rst 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 rst and maximum lateness LEDD = T 1. ELS/IIT algorithm generates optimal schedule LELS = r and Lopt = r;
The example 2 from [
Algorithm for constructing an optimal schedule The branch and bound algorithm produces a feasible IIT schedule for a xed 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 de le interval (a; b] such as a < Lopt b:
First we de ne the low bound of maximum lateness. We calculate two low bounds and
LB1 = maxfr(ui) + t(ui)
D(ui)jui 2 U g n LB2 = maxf∑ t(ui) i=1
Dmaxg: Then the low bound of maximum lateness LB is
LB = maxfLB1; LB2g:
The upper bound b = ∑in=1 t(ui) + rmax Dmin [
Select z = ⌈(a + b)=2⌉ and use branch and bound method for constructing a feasible schedule BB(U; D + z; S): If we nd a feasible schedule then we take interval (a; z], else we take interval (z; b] and repeat .
Algorithm SCHEDU LE(U ; Sopt; Lopt)
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 = maxfD (ui)jui 2 U g 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 nd 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 xed 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 de nition 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.
De nition 1. The solution n = (l1; l2; : : : ; ln) is called the extension of partial solutions k = (q1; q2; : : : ; qk), if l1 = q1; l2 = q2; : : : ; lk = qk.
De nition 2. A partial solution k, which is a feasible schedule.
k is called a feasible if there exists an extension of 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 2 U; the start time of its execution (ui) satis es the inequality r(ui) (ui)
vmax(ui): 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 idle time of processor in the feasible schedule S of length Dmax, then I = Dmax ∑in=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.
De nition 3. Task u 2= k is called the ready task at the level k, if r(u) satis es the inequality r(u) tmin(k) I ∑u2 k idle(ui):
The main way of reducing of the exhaustive search will be the earliest possible identi cation unfeasible solutions.
De nition 4. Let the task ucr 2= k is such as vmax(ucr) = minfvmax(u)ju 2= The task ucr 2= k is called the delayed task for k, if vmax(ucr) < tmin(k). kg:
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 maxftmink
k 1 [ u is unfeasible. 3. If maxftmin(k 1); r(ucr)g + t(ucr) > vmax(uk) then the partial solution unfeasible.
1; r(u)g + t(u) > vmax(ucr) a partial solution k 1 is Proof. 1. This follows from de nition 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 maxftmin(k); r(u)g + 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) = maxftmin(k 1); r(ucr)g + t(ucr):
On lemma maxftmin(k 1); r(ucr)g + 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. Algorithm 1 BB/IIT algorithm
Another method for determining unfeasible partial solutions based on a
comparison of resource requirements of tasks and processor power. In this case we propose to
modify the algorithm for determining the interval of concentration [
We consider time intervals [t1; t2] [tmin(k); Dmax].
For all tasks ui 2= k we nd minimal time of its begin: v(ui) = maxfr(ui); timekg. 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) = ∑ minfL(xk(ui)); L(y(ui))g; ui2= k where
Let
xk(ui) = [v(ui); v(ui) + t(ui)] \ [t1; t2]; y(ui) = [vmax(ui); vmax(ui) + t(ui)] \ [t1; t2]: est( k) =
max [t1;t2]2[tmin(k);Dmax] fMk(t1; t2) (t2 t1):g 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. In this paper we propose IIT schedule for 1jrj jLmax problem. We propose an approximate 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 xed maximum lateness L. The algorithm may be used in a binary search mode to nd 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.