The Continuous Task Scheduling Problem: Formulations and a Constraints-Relaxation and Decomposition Approach

ABSTRACT

We consider the problem of scheduling independent unit-execution-time tasks on unrelated processors, each having the work and rest time restrictions. The objective is to find a continuous schedule can complete all tasks with the shortest makespan. We provide one integer programming formulation for the continuous scheduling problem for at least one processor, formulation for at least one processor, and one for at most some processors working at each time period. We also relax the constraints and decompose those formulations into their sub-models respectively. We will provide the comparisons of the computational results of each of the “full model” with those of the corresponding “relaxed and decomposed model”. An integer programming package GAMS-ZOOM【2】 will be the solver for all the models under the PC equipment. The result shows constraints-relaxation and decomposition approach is a very good approximation for all those corresponding full models.

INTRODUCTION

The problem of continuous scheduling of n independent unit-execution-time tasks on m unrelated multiprocessors with work/rest time restrictions is studied【4】. Such problem starts with a set J={J1,J2,…,Jn} of n tasks and a set P={P1,P2,…,Pm} of m processors. Processor Pi can only execute a nonempty subset Si J of tasks and We assume that no processor can work without any rest. That is, each processor, after work for a
certain periods, must rest for a predetermined elapse of time. A max mork time Wi and a min rest time Ri for each Pi, . Each processor Pi can continuously work for at max wi time units. A schedule is called feasible if and only if every task is assigned a processor that can execute it, and in each time unit of the makespan, at least one or some processors are working. An optimal schedule is the schedule that has the shortest makespan among all possible feasible schedules【5】. The objective is to find an optimal feasible schedule if one exists. We note here that the 3-PARTITION problem【1】 which is NP-compete in the strong sense which can be polynomially reduced to the continuous task scheduling problem defined here.Therefore, the continuous task scheduling problem is itself NP-complete in the strong sense【3】.

AN INTERGER PROGRAMMING FORMULATION

Let us now define the parameters and variables for the formulation:
m: the number of processors.
n: the number of tasks.
Ij={the processor which can execute task j}.
Wi: an integer≧1, max continuously working time for processor i
Ri: an integer≧0, min continuously resting time for processor i
M: the makespan
Xijk=1, if task j is executed by processor i in time unit k; otherwise equal to 0, where , if processor i executes a task in time unit k; otherwise, equal to 0. and . Using the notations defined above, the continuous task scheduling problem for the at-least-one-processor-working requirement (denoted as Model [ALl]) can be formulated as an integer program below.
Model [ALl]
Minimize M(1)
Subject to:
(2)
j=1,.....,n(3)
(4)
(5)
(6)

(7)
(8)

The objective (1) is to minimize the makespan, which is defined by constraint (2). That is, the makespan is the largest index of the time period which at least a processor is working. Constraint (3) ensures that all tasks are scheduled and each task is scheduled exactly once. Constraint (4) defines the Zik variables by relating the Zik variables with the Xijk variable. Constraint (5) ensures that there is at least one processor working in every time unit of the makespan. After all tasks are scheduled, the second term of (5) becomes 1, and this results in , a redundant constraint. Constraint (6) ensures that each processor meets the minimum resting time requirement once it begins to rest. There are four possible pairs of values for (Zi,k-1, Zik) namely, (0,0), (0,1), (1,0), (1,1), that indicate the work/rest conditions of processor i in time periods k-1 and k. Note that only in the case of (1,0) is constraint (6) is effect, which corresponds to the situation where processor i switches from working (in time period k-1) to resting (in time period k). In this case, the summation of Ziq values from q=k to k+ri-1is forced to equal 0. The other three possible pairs of ( Zi,k-1, Zik) values will result in redundant constraint. Constraint (7) ensures that processor i does not work for more than wi time for every i. Finally, Constraint (8) specifies that the decision variables are of binary values.

If we remove constraints (3) and (4), the model will contain only four set of constraints and i*k binary variables. This formulation can be named as Model 【Zik】. Solving this formulation gives Zik, which shows whether processor i is working in time unit k. After that, we can solve Model 【Xij】to obtain the task-to-processor assignments.
The model [Xij] is listed below:
Model [Xij]

Let Zsum(i) be the sum of tasks that are assigned to processor i, where , are obtained by solving Model [Zik].
(9)
(10)
(11)
(12)
The [ALl] model has been decomposed into two sub-model [Zik] and [Xij]. In the [Zik] model, we remove the constraints (3) and (4) of [ALl], and this model is equivalent to an assignment problem, which will provide the processor to time period assignment matrix. Note here that the solution may or may not be feasible. The [Xij] model is a transportation model, where we seek to obtain a feasible schedule using an input the solution to solve the [Zik] and [Xij] models sequentially and iteratively until an optimal solution to the original problem is found. We begin by solving the [Zik] model. A minimum makespan M and corresponding matrix Z are obtained. This assignment matrix indicates which processors will execute tasks in a given time period. Again, the Z matrix may or may not be feasible. We then feed Zik matrix into the [Xij] model and solve it. If the Z matrix is feasible, then the solution to the [Xij] model will give us the optimal schedule. If the Z matrix is not feasible, we then return to the [Zik] model, add one additional constraints M M*+1, to enlarge the feasible region of the current makespan M* (because relaxing the constraints may get underestimate makespan), and resolve the [Zik] model, We can use the feasible / infeasible signal from the [Xij] model to determine whether if we reach an optimal schedule or not. Such procedure has been automated by using GAMS. The number of iterations is set equal to 25, but usually the procedure terminates with only a fraction of the above limit on the number of iterations.