On a methodology for discrete–continuous scheduling

Abstract

Discrete–continuous problems of scheduling nonpreemptable jobs on parallel machines are considered. The problems arise e.g. when jobs are assigned to multiple parallel processors driven by a common electric, hydraulic or pneumatic power source. Existing models have assumed job processing rates as a function of the number of jobs currently being processed, or equivalently the number of machines currently in operation. In this paper a more general model is proposed in which processing rates of a job assigned to a machine depend on the amount of a continuous, i.e. continuously divisible resource (e.g. power) allotted to this job at a time. Thus the problem consists of two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to allocate the continuous resource among jobs already sequenced. We provide a comprehensive analysis of the problem. This includes properties of optimal schedules, efficiently (in particular analytically) solvable cases, formulations of the possibly simplest mathematical programming problems for finding optimal schedules in the general case, heuristics and the worst-case analysis. Although our objective function in this paper is to minimize makespan of a set of independent jobs, the presented methodology can be applied to other criteria, precedence-related jobs, and many resource types (apart from, or instead of machines).

Introduction

In the classical model of discrete scheduling problems on parallel machines under additional resources, the last ones can be allotted to jobs in amounts (numbers of units) from given finite sets only. In consequence, each job is characterized by a vector of processing times representing all its alternative performance modes. Within this model a number of results are known in the literature, concerning the computational complexity and exact and approximation algorithms (see e.g. Błażewicz et al., 1994). However, in many practical situations additional resources can be allotted to jobs in amounts (unknown in advance) from given intervals. Such resources may be called continuously divisible or simply continuous. These may be, among others, the situations when jobs are assigned to parallel processors driven by a common (electric, hydraulic, pneumatic) power source, e.g. commonly supplied grinding or mixing machines, electrolytic tanks or refuelling terminals. As another example one can consider the forging process in steel plants (Janiak, 1989). Forgings are preheated by gas up to an appropriate temperature in forge furnaces. Gas flow intensity, limited for the whole battery of forge furnaces, is a continuous resource. Also in computer systems multiple processors may share a common primary memory. If it is a paged-virtual memory system and the number of pages goes into hundreds, primary memory can be treated as a continuous resource (see Węglarz, 1980). On the other hand, in scalable (SPP) and massively parallel (MPP) systems with hundreds or even thousands of processors, processors themselves can be considered as the continuous resource and the role of the machines can be played e.g. by disk drives.

In the situations of the type presented each job can be described by a continuous function relating its processing time or rather processing rate, to the amount of the continuous resource allotted to this job. In consequence, we search simultaneously for a sequence of n jobs on m machines and a continuous resource allocation which optimize a given schedule performance measure. Thus, from the viewpoint of the (generally understood) resources involved, we can speak about discrete–continuous scheduling problems, where parallel machines are the discrete resource.

It should be stressed that the discrete–continuous approach may be successfully applied also to discrete problems, i.e. those in which we know in advance possible resource allocations (job performance modes). This is because this approach allows us to prove some general properties of optimal schedules. Knowledge of these properties is very useful in the construction and analysis of scheduling algorithms, and can even lead to analytical results. We shall demonstrate this referring to the following practical problem described in Dror et al. (1987). Let m refuelling terminals driven by a common power source (a pump) be used to refuel a given fleet of n boats. The decision problem is: Are the present refuelling facilities capable of fully refuelling a given fleet within a certain critical time? The corresponding optimization problem can be formulated as a makespan scheduling problem for the fleet of boats. The proportion of the output of the pump for a terminal can be treated as a continuous resource, although its possible allocations are known in advance and equal to 1/Y(t), where Y(t)∈{1,2,…,m} is the number of terminals in operation at time t. We show that our approach generalizes the results obtained for the discrete formulation. We refer to the paper by Dror et al. (1987) since it is the first one dealing with problems belonging to the class we are interested in. However, our methodology is applicable to a much larger class of problems. This is because the methodology deals with the entire, discrete–continuous nature of the problems and explores interrelations between both the components. For clarity we concentrate on the case of independent, nonpreemptive jobs (for the preemptive case corresponding problems were studied in Węglarz, 1980, but this case does not need a special methodology in comparison with the problem of allocating continuous resources only), identical machines, a single continuous, renewable resource, and schedule length (makespan) as a performance measure. We assume that each machine can process at most one job at a time, and that all jobs and machines are simultaneously available at the start of the process. Nevertheless, the methodology presented is not restricted to the class of problems described above and can be generalized in a number of directions.

In Section 2we present a general formulation of the considered class of problems and show that the problems studied by Dror et al. (1987) are a subclass of this class. 3 Optimal schedules for, 4 Optimal schedules forare devoted to the finding of optimal schedules for n⩽m and n > m, respectively. In Section 3several analytical results are proved, based on the properties of optimal continuous resource allocations, whereas in Section 4the problem of finding optimal schedules for arbitrary concave job models is reduced to the solution of some convex programming problems. This section also creates a basis for the construction of some heuristics which are described and evaluated in Section 5. Suggestions for further research are given in Section 6.