Scheduling parallel tasks with due dates

We consider the problem of scheduling independent parallel tasks in a system with identical parallel processors. Given a set of n tasks or jobs A = (A_1, A_2, ..., A_n ), each having specified its own execution time d_i, that require a fixed number n_i of processors or resources, i.e. their size (non-malleable). Tasks in A are mutually independent, that is, there are no precedence constraints nor data communication among the tasks. Once job A_i starts to execute, it runs without interruption until it completes, i.e. there is no pre-emption. The jobs may have a weight according to their importance, earliest start times (or release dates) and due dates. If we omit these, the resulting cutting problem is of the non-guillotine type. Sometimes the problem is also called minimum strip or 2D rectangular packing. We are interested in a high resource utilization of the different processors, in time delivery dates or finishing times for the jobs, if possible, and a kind of fairness between the tasks. The objective is to find a non-preemptive schedule of A that minimizes the weighted quadratic tardiness of the set of jobs processed thus trying to meet their due dates. The most straightforward way to schedule a multiprocessor machine is to search for the earliest time the task will fit and to schedule it there. However, this may not be the most efficient way to set the schedule. In particular, jobs which request a large number of processors can tie up the system, possibly delaying several tasks which require fewer processors, yet leaving a few processors idle. In industrial practice heuristics are widely used to decide, which task or job is the next to be processed on the next available resource. To schedule berthing priorities, very often the scheduling policy used is FCFS. The computation requirements for these rules, that use criteria like slack, processing times or many others, are moderate. Genetic algorithms have been applied too. But in general there is no way to tell, if the resulting schedule is good or not, unless the optimum is known. Enumerative methods that find the optimum, still need a prohibitive amount of computation time for even rather small problem sizes. It is unlikely that a polynomial time algorithm exists, as the problem is NP-hard, since it includes the bin packing problem as a special case when all tasks have unit execution time. Therefore we present an algorithm that finds a near-optimal solution for the scheduling problem of scarce resources processing the given tasks, whose computational effort grows just linear in the number of jobs and supplies guaranteed precision bounds for the distance to the optimum by using Lagrangian relaxation. The modification of the multipliers is done via a subgradient technique and a heuristic then gets a feasible solution. Often the problem of scheduling multiprocessor machines may be viewed as fitting rectangles representing the number of resources times the processing time into a grid of available resources. This scheduling problem looks similar to the two dimensional rectangle packing problem, where each task A_i is treated as a rectangle with width n_i and height d_i. The rectangle packing model implies that processors should be allocated in contiguous groups. Such a scheduling problem arises in parallel systems like linear arrays or the ship berth assignment and scheduling. There may be slight differences in the side-constraints, for example in cutting problems it might be admitted to turn the strip needed by 90 degrees, whereas in packing problems this may not be allowed. Contiguous processor allocation is required in these cases and we provide solutions for it. Other applications in parallel computing systems such as symmetric shared memory multiprocessors, distributed computing systems such as bus-connected networks of workstations and the scheduling of a crew of equally trained people do not have this constraint. In these systems, a processor allocation mechanism is independent of the topology of an interconnection network. We tested our algorithm as well on the examples of Hopper/Turton (EJOR 2000). It must be pointed out, however, that in contrary to ours their problem definition allows to turn the strips by 90 degrees. We tested as well some problems where the number of processors and time units needed are interchanged and state the performance measures. The maximal tardiness times the number of processors determines the minimal rectangle found. In the first three cases an optimal solution is found either way. The others show very close solutions in most cases and less than 10 % from the optimum in a few. However, some of the deviations may be caused by the slightly different problem definition.