Task scheduling in parallel processor systems

Abstract

Task scheduling in parallel processing systems is one of the most challenging industrial problems. This problem typically arises in the manufacturing and service industries. The task scheduling problem is to determine a set of task assignments to a set of parallel processors for execution so as to optimize a specified performance measure. The difficulty of the problem is that the scheduling needs to satisfy a set of requirements as well as a range of environmental constraints. The problem is known to be NP-complete.In this study, we consider a non-preemtive task scheduling problem on iden- tical and unrelated parallel processor systems. We are interested in the objective function that minimizes the maximum of the completion time of the entire set of tasks (i.e makespan) so as to ensure a good load balance on the parallel proces- sors. We consider three different task characteristics to the classical task scheduling problem that has a set of n independent tasks to be assigned to m parallel processors.The first task characteristic that we consider is an on-line scheduling with release date specifications on an identical parallel processing system with a centralized queue and no splitting structure. We focus on developing simple and efficient heuristics for this problem. Three heuristic algorithms are proposed to solve this non-deterministic problem with scheduling over time where the availability of each task is restricted by release date. Our approach uses a multi-step method in the task selection phase and a greedy search algorithm in the processor selection phase. The multi-step method is used to reduce the non-determinism in on-line scheduling by partitioning the scheduling process into several procedures. We introduce two procedures in the priority rule loop which we refer to as Cluster Insertion and Local Cluster Interchange.Computational testing on randomly generated data is conducted using Microsoft Visual C++ 6.0 to examine the effectiveness of the proposed multi-step method against the optimal solution. Different size of problems are tested in the experiment involving 3 processors by 200 tasks up to 5 processors by 1000 tasks with five clusters ranging from 10 to 50. The computational results show that all the three heuristics performed very well with the value of the average gaps are improved as the number of the tasks in the system is increases. The average gap for all the three heuristics are less than 1.04% for the largest tested cases (i.e for 1000 tasks run on 5 processors).In the second problem, we address priority consideration as an added feature to the basic task characteristics of unrelated parallel processors scheduling. The priority consideration is defined by a list of ordered independent tasks with priority. A task requires to start processing after another task is finished on the same processor based on priority but may require to start earlier if processed on other machine. Our aim is to develop Mixed Integer Linear Programming models to obtain optimal solutions for three type of priority lists which are ascending order, descending order and general priority list. We validate the model using a case study taken from the literature. Then, computational testing is implemented on the general priority list using AIMMS 3.10 package and CPLEX 12.1 as the solver. Computational results show that the proposed MILP model is effective and produces optimal results for all tested cases. The model is very efficient as 95% of all the instances, which are problem up to 80 tasks assigned on 5 processors, have been solved within 5 minutes of CPU time.In the final problem, we address a further problem for the task scheduling with a disruption problem that occurs on the parallel processor system. The disruption is causes by the unavailability of the processor during a certain time and it is called resource disruption. Our recovery solution for the disruption problem is a rescheduling approach. A MILP model is developed for the rescheduling model for the case of non-resumable tasks. Recovery model for the disrupted initial schedule with dummy insertion is proposed for predictive disruption management and match up schedule for post-disruption management. To evaluate the model, computational testing is performed with different sets of data.Different levels of disruptions are considered with different weights in the objective function to observe the stability of the model. The optimum initial schedule and the rescheduling model is performed using CPLEX 12.1 solver in AIMMS 3.10 package. In our computational results we measure the stability rate which is to observe the stability condition of the current schedule compared to the initial schedule in term of the task migration. From the results, the stability is improved when the number of tasks in the system increases within a reasonable amount of time. Another interesting observation is that our model yields small average gaps that are less than 7.99% within 300 seconds of the CPU time for a large data set that reach 200 tasks by 10 processors. The average gaps are considerably small for the disruption problem since the rescheduling model have to match up with the optimum initial schedule.