Formulating and Decomposing the Continuous Task Scheduling Problem -

Details for Formulating and Decomposing the Continuous Task Scheduling Problem

ID:	2495
Author:	Dr. Henry T. Yeh
Title:	Formulating and Decomposing the Continuous Task Scheduling Problem
Article:	CTSP): AT LEAST SOME PROCESSORS WORKING ON EVERY TIME PERIOD 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 p (p 1) processor, formulation for at least some processors, and one for at most some processors working at each time period. We also relax the constraints and decompose those formulations into their submodels 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 (Brooke Meeraus, 1988) will be the solver for all the models under the personal computer environment. The result shows constraints-relaxation and decomposition approach is a very good approximation for all those corresponding full models. 1. Introduction The problem of continuous scheduling of n independent unit-execution-time tasks on m unrelated multiprocessors with work/rest time restrictions is studied. Such problem starts with a set J={J1,J2,…,Jn} of n tasks and a set P={P1,P2,…,Pm} of m processors (Chang Lee, 1988). Processor Pi can only execute a nonempty subset Si J of tasks and . We assume that no processor can work without any rest (Chen Lai, 1988). 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. The objective is to find an optimal feasible schedule if one exists. We note here that the 3-PARTITION problem (Garey Johnson, 1978) which is NP-compete in the strong sense which can be polynomially reduced to the continuous task scheduling problem defined here (Carreno, 1990). Therefore, the continuous task scheduling problem is itself NP-complete in the strong sense. 1.1 Application The continuous task scheduling problem can be applied in many cases, for example, in the airline industry, United Airline requires at least p (p 1) pilots flying all the time. The company consists of several (m) pilots with n airplanes. Each pilot has its own flying capability according to the regulation by FAA, a maximum working time wi and a minimum resting time ri. Our goal is to find a continuous flying schedule that at every time unit there are at least p pilots flying where 1#8806;p#8806;m. That is, the company does not desire all pilots to rest simultaneously. If that happens, the efficiency and profits of the entire company will deteriorate. Furthermore, our goal is to find the shortest one among all possible feasible continuous schedules. 2. An integer 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#8807;1, max continuously working time for processor i Ri: an integer#8807;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-p-processor-working requirement (denoted as Model [ALp]) can be formulated as an integer program below. Model [ALp] 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. 3. A constraints-relaxation and decomposition approach Let us difine again: , where p is an integer number and k=2,…,n If we add four more constraint (9),(10),(11),(12), then will make the C1=1 (9) (10) (11) (12) 3.1 Submodel [Zik] Variable Ck is 1 as long as at least p tasks remain to be scheduled; Constraint (9) initializes Ck for the first tiem unit. Constraint (10) ensures that at least p processors are working in every time unit until all n tasks have been completed, which also means that there are always at least p remaining tasks to be scheduled at time period k until al tasks are completed. It forces Ck to 0 after all tasks have been scheduled. This is critical for the next two constraints to work. Constraint (11) ensures that at least p processors are working in every time unit when there are at least p remaining tasks to be scheduled (i.e., when Ck =1). After all tasks are completed, Constraint (11) becomes redundant (i.e., when Ck =0). Constraint (12), together with Constraint (5) will force Ck to be 1 if there are tasks remaining unscheduled. If we remove constraints (3) and (4), the model will contain only four set of constraints and ik binary variables. This formulation can be named as Model #12304;Zik#12305;. Solving this formulation gives Zik, which shows whether processor i is working in time unit k. After that, we can solve Model #12304;Xij#12305;to obtain the task-to-processor assignments. 3.2 Submodel [Xij] 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]. (13) (14) (15) (16) The [ALp] model has been decomposed into two sub-model [Zik] and [Xij]. In the [Zik] model, we remove the constraints (3) and (4) of [ALp], 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. 4. Experimental design and results We tested the integer programming formulation for model is [CTSP], [Z] and [X], where m=5, 10 with wi / ri=(5, 10, 10) and (5, 8, 10) ,N=60, 80, 100, t(Jj)=2, 3, 4, n=30, 40, 50, 20, 15, 25, by using a commercially available linear programming code. GAMS (General Algebraic Modeling Systems) on an PC. Computation is truncated for excessive time or storage requirement using truncation for excessive time or storage requirement using truncation criteria of maximum nodes=100,000. maximum # of branch-and-bound steps=1,000,000. We compared their makespen, number of the iteration of the procedure, and CPU times. The experimental results are listed as follows. Table 1 Computational Results M N N T(Jj) wiri MAKESPAN # OF ITERATIONS CPU TIME Models Models Models [Z] [X][CTSP] [CTSP] [Z][X] [CTSP] [Z][X] [CTSP] [Z][X] 5 60 30 2 5 14 14 1 13 295.4 222.4 75% 80 40 10 17 17 1 16 479.4 384 80% 100 50 3 10 22 22 1 21 902 781.28 85% 60 20 4 5 14 14 1 13 295.4 222/4 75% 60 15 5 14 14 1 13 295.4 222.4 75% 80 20 10 17 17 1 16 479.4 384 80% 100 25 10 22 22 1 21 902 781.28 85% 10 60 30 2 5 7 7 1 6 141.4 112 79% 80 40 8 8 8 1 7 211.2 176 83% 100 50 3 10 10 10 1 9 377 299.7 88% 60 20 4 5 7 7 1 6 141.4 112 79% 60 15 5 7 7 1 6 141.4 112 79% 80 20 8 8 8 1 7 211.2 176 83% 100 25 10 10 10 1 9 337 299.7 88% 5 Discussion From the table 1, we know two submodels [Z] and [X] have the same makespen, this demonstrated the accuracy of the relaxation and decomposition procedure. It is interesting that the iterations of the model [Z] and [X] are equal to makespan -1, it is because that it the matrix is not feasible, then we return to the model [Z] and add one additional constraint , such procedure makes every iteration increase one makespen until we reach the optimal solution. The CPU time of model [Z] and [X] is approximately 83% of the mode [CSP], this show model [Z] and [X] is mode efficiency that model [CSP] with the condition not sacrificing the optimally. The larger size problem instance of the model [Z] and [X], the larger ratio of CPU time between the models [Z], [X] and [CSP], which is reasonable, because the larger problem size will occupy more computer memories on model [Z] and [X] and will take more computational CPU time. We have decomposed the exact integer-programming model into two subproblem models and run the experiments on both models. It shows the constraint-relaxation and decomposition approach is more efficient than the original model without sacrificing the optimality. The computational results show the constraint- relaxation / decomposition approach is a good approximation for the corresponding model [ALp]. About the author of this article: dr. henry t. yeh received his ph.d. in business, mba degrees from baruch college, cuny in the 90s and ms degree in operations research from columbia university. he has taught at cuny and st. john’s university and worked at twa. he is currently teaching at southwest international university usa.
Category:	Business: Management
Date:	April 15, 2009 12:02:55 PM

Advertising