Scheduling precedence graphs of bounded height

The existence of a schedule for a partially ordered set of unit length tasks on m identical processors is known to be NP-complete (J. D. Ullman, NP-complete scheduling problems, J. Comput. System Sci., 10 (1975), 384–393). The problem remains NP-complete even if we restrict the precedence graph to be of height bounded by a constant. (J. K. Lenkstra and A. H. G. Rinnooy Kan, Complexity of scheduling under precedence constraints, Operations Res., 26 (1978), 22–35; D. Dolev and M. K. Warmuth, “Scheduling Flat Graphs,” IBM Research Report RJ 3398, 1982). In these NP-completeness proofs the upper bound on the number of available processors varies with the problem instance. We present a polynomial algorithm for the case where the upper bound on the number of available processors and the height of the precedence graph are both constants.     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为$2-\frac 2m$,其中$m$是机器数目。     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题，目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时，两类问题在一般优先图上都是强NP-困难的，而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界，并基于许可工件之间的最大匹配设计近似算法，其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题，我们在理论上证明了算法的近似比为$2-\frac 2m$，其中$m$是机器数目。     

An iterative algorithm for scheduling UET tasks with due dates and release times

A new polynomial-time iterative algorithm is presented for the scheduling problem with a unit execution time task system, parallel identical processors, precedence constraints, release times, and the criterion of maximum lateness. For the maximum lateness and makespan problems the algorithm allows to achieve the performance guarantees previously known only for the problems without release times.     

Multiprocessor scheduling under precedence constraints: Polyhedral results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.     

General scheduling non-approximability results in presence of hierarchical communications

We investigate on the issue of minimizing the makespan (resp. the sum of the completion times) for the multiprocessor scheduling problem in presence of hierarchical communications. We consider a model with two levels of communication: interprocessor and intercluster. The processors are grouped in fully connected clusters. We propose general non-approximability results in the case where all the tasks of the precedence graph have unit execution times, and where the multiprocessor is composed of an unrestricted number of machines with l ? 4 identical processors each.     

Periodic schedules for linear precedence constraints

We consider the computation of periodic cyclic schedules for linear precedence constraints graphs: a linear precedence constraint is defined between two tasks and induces an infinite set of usual precedence constraints between their executions such that the difference of iterations is a linear function. The objective function is the minimization of the maximal period of a task.We recall first that this problem may be modelled using linear programming. A polynomial algorithm is then developed to solve it for a particular class of linear precedence graphs called unitary graphs. We also show that a periodic schedule may not exist for unitary graphs. In the general case, a decomposition of the linear precedence graph into unitary components is computed and we assume that a periodic schedule exists for each of these components. Lower bounds on the periods are exhibited and we show that an optimal periodic schedule may not achieve them. The notion of quasi-periodic schedule is then introduced and we prove that this new class of schedules always reaches these bounds.     

Approximations for the Two-Machine Cross-Docking Flow Shop Problem

We consider in this article the Two-Machine Cross-Docking Flow Shop Problem, which is a special case of scheduling with typed tasks, where we have two types of tasks and one machine per type. Precedence constraints exist between tasks, but only from a task of the first type to a task of the second type. The precedence relation is thus a directed bipartite graph. Minimizing the makespan is strongly NP-hard even with unit processing times, but any greedy method yields a 2-approximation solution. In this paper, we are interested in establishing new approximability results for this problem. More specifically, we investigate three directions: list scheduling algorithms based on the relaxation of the resources, the decomposition of the problem according to the connected components of the precedence graph, and finally the search of the induced balanced subgraph with a bounded degree.     

Sequencing with uncertain numerical data for makespan minimisation

We consider a scheduling problem with the objective of minimising the makespan under uncertain numerical input data (for example, the processing time of an operation, the job release time and due date) and fixed structural input data (for example the precedence and capacity constraints). We assume that at (before) the scheduling stage the structural input data are known and fixed but all we know about the numerical input data are their upper and lower bounds, where the uncertain numerical data become realised at the control stage as the scheduled process evolves. After improving the mixed graph model, we present an approach for dealing with our scheduling problem under uncertain numerical data based on a stability analysis of an optimal makespan schedule. In particular, we investigate the candidate set of the critical paths in a circuit-free digraph, characterise a minimal set of the optimal schedules, and develop an optimal and a heuristic algorithm. We also report computational results for randomly generated as well as well-known test problems.     

Task scheduling with and without communication delays: A unified approach

The problem of scheduling directed acyclic task graphs on an unbounded number of processors is considered. We present a single algorithm which is applicable to several special cases, thus effecting a unified approach to task scheduling independent of the task graph. We start by considering multi-stage dags and present an algorithm that computes a schedule in O(Nq log q) time, where N is the number of stages, and q is the maximum number of edges between any two stages of the graph. We show that the schedule produced by the algorithm is optimal when: (i) all communication delays are zero or, (ii) the precedence graph is an in-tree or an out-tree and communication times are small or, (iii) the task graph is densely connected and communication costs and processing costs are unity. For multi-stage dags with small communication times we show that the makespan of the schedule generated by our algorithm is less than twice that of the optimal. We also bound the makespan for the case when communication times are arbitrary. We then show how the algorithm may be applied to schedule arbitrary dags and derive the performance bounds for this case. Finally, we present the results of tests we carried out with randomly generated task graphs. These seem to indicate that, on the average, the algorithm performs substantially better than theoretical worst case predictions.     

Scheduling tasks and communications on a virtual distributed system

A set of tasks has to be scheduled on identical parallel processors subject to precedence constraints and small communication delays. A polynomial algorithm is known to exist if task duplication is allowed and the number of available processors is not limited. However the problem of communications scheduling is not taken into account. In this paper, we prove that this algorithm also never saturates communication channels and always delivers messages on time, if slightly stronger constraints are imposed on the tasks.     

Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap

Coupled tasks scheduling was originally introduced for modelling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on one processor, under the assumptions that all processing times are equal to 1, the gap has a constant exact length and the precedence constraints are strict. Although it is proven that the problem stated above is NP-hard in the strong sense if the precedence constraints have a form of a general graph, it is possible to solve some of its relaxed versions in polynomial time. This paper contains a solution for the problem of coupled tasks scheduling with an assumption that the precedence constraints graph has a form of chains and it presents an algorithm that can solve the problem with such assumption in time O(n?log?n).     

Scheduling UET task systems with concurrency on two parallel identical processors

Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family.     

The complexity of a cyclic scheduling problem with identical machines and precedence constraints

We consider a set T of tasks with unit processing times. Each of them must be executed infinitely often. A uniform constraint is defined between two tasks and induces a set of precedence constraints on their successive executions. We limit our study to a subset of uniform constraints corresponding to two hypotheses often verified in practice: Each execution of T must end by a special task f, and uniform constraints between executions from different iterations start from f. We have a fixed number of identical machines. The problem is to find a periodic schedule of T which maximizes the throughput. We prove that this problem is NP-hard and show that it is polynomial for two machines. We also present another nontrivial polynomial subcase which is a restriction of uniform precedence constraints.     

A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time.     

Computing optimal preemptive schedules for parallel tasks: linear programming approaches

 We study the problem of scheduling a set of n independent parallel tasks on m processors, where in addition to the processing time there is a size associated with each task indicating that the task can be processed on any subset of processors of the given size. Based on a linear programming formulation, we propose an algorithm for computing a preemptive schedule with minimum makespan, and show that the running time of the algorithm depends polynomially on m and only linearly on n. Thus for any fixed m, an optimal preemptive schedule can be computed in O(n) time. We also present extensions of this approach to other (more general) scheduling problems with malleable tasks, due dates and maximum lateness minimization. Received: November 1999 / Accepted: November 2002 Publication online: December 19, 2002 RID="⋆" ID="⋆" This work was done while the authors were associated with the research institutes IDSIA Lugano and MPII Saarbrücken and were supported in part by the Swiss Office Fédéral de l'éducation et de la Science project n 97.0315 titled ``Platform' and by EU ESPRIT LTR Project No. 20244 (ALCOM-IT)     

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal

The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.     

Decentralized list scheduling

Classical list scheduling is a very popular and efficient technique for scheduling jobs for parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors, the cost for managing a single centralized list becomes too prohibitive. A suitable approach to reduce the contention is to distribute the list among the computational units: each processor only has a local view of the work to execute. Thus, the scheduler is no longer greedy and standard performance guarantees are lost. The objective of this work is to study the extra cost that must be paid when the list is distributed among the computational units. We first present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load imbalance between the local lists. We obtain an equation giving the evolution of the potential by computing its expected decrease in one step of the schedule. Our main theorem shows how to solve such equations to bound the makespan. Then, we apply this method to several scheduling problems, namely, for unit independent tasks, for weighted independent tasks and for tasks with precedence constraints. More precisely, we prove that the time for scheduling a global workload W composed of independent unit tasks on m processors is equal to W/m plus an additional term proportional to log₂ W. We provide a lower bound which shows that this is optimal up to a constant. This result is extended to the case of weighted independent tasks. In the last setting, precedence task graphs, our analysis leads to an improvement on the bound of Arora et al. (Theory Comput. Syst. 34(2):115–144, 2001). We end with some experiments using a simulator. The distribution of the makespan is shown to fit existing probability laws. Moreover, the simulations give a better insight into the additive term whose value is shown to be around 3log₂ W confirming the precision of our analysis.     

Time complexity of single- and identical parallel-machine scheduling with GERT network precedence constraints

In this paper we deal with the time complexity of single- and identical parallel-machine scheduling problems in which the durations and precedence constraints of the activities are stochastic. The stochastic precedence constraints are given by GERT networks. First, we sketch the basic concepts of GERT networks and machine scheduling with GERT network precedence constraints. Second, we discuss the time complexity of some open single-machine scheduling problems with GERT network precedence constraints. Third, we investigate the time complexity of identical parallel-machine scheduling problems with GERT network precedence constraints. Finally, we present an efficient reduction algorithm for the problem of computing the expected makespan for the latter type of scheduling problem.