Little-Preemptive Scheduling on Unrelated Processors

We consider the preemptive scheduling of n independent jobs on m unrelated machines to minimize the makespan. Preemptive schedules with at most 2m–3 preemptions are built, which are optimal when the maximal job processing time is no more than the optimal schedule makespan. We further restrict the maximal job processing time and obtain optimal schedules with at most m–1 preemptions. This is better than the earlier known best bound of 4m ²–5m+2 on the total number of preemptions. Without the restriction on the maximal job processing time, our (2m–3)-preemptive schedules have a makespan which is no more than either of the following two magnitudes: (a) the maximum between the longest job processing time and the optimal preemptive makespan, and (b) the optimal nonpreemptive makespan. Our (m–1)-preemptive schedules might be at most twice worse than an optimal one.     

On the geometry,preemptions and complexity of multiprocessor and shop scheduling

In this paper we study multiprocessor and open shop scheduling problems from several points of view. We explore a tight dependence of the polynomial solvability/intractability on the number of allowed preemptions. For an exhaustive interrelation, we address the geometry of problems by means of a novel graphical representation. We use the so-called preemption and machine-dependency graphs for preemptive multiprocessor and shop scheduling problems, respectively. In a natural manner, we call a scheduling problem acyclic if the corresponding graph is acyclic. There is a substantial interrelation between the structure of these graphs and the complexity of the problems. Acyclic scheduling problems are quite restrictive; at the same time, many of them still remain NP-hard. We believe that an exhaustive study of acyclic scheduling problems can lead to a better understanding and give a better insight of general scheduling problems. We show that not only acyclic but also a special non-acyclic version of periodic job-shop scheduling can be solved in polynomial (linear) time. In that version, the corresponding machine dependency graph is allowed to have a special type of the so-called parti-colored cycles. We show that trivial extensions of this problem become NP-hard. Then we suggest a linear-time algorithm for the acyclic open-shop problem in which at most m−2 preemptions are allowed, where m is the number of machines. This result is also tight, as we show that if we allow one less preemption, then this strongly restricted version of the classical open-shop scheduling problem becomes NP-hard. In general, we show that very simple acyclic shop scheduling problems are NP-hard. As an example, any flow-shop problem with a single job with three operations and the rest of the jobs with a single non-zero length operation is NP-hard. We suggest linear-time approximation algorithm with the worst-case performance of ( , respectively) for acyclic job-shop (open-shop, respectively), where (‖ℳ‖, respectively) is the maximal job length (machine load, respectively). We show that no algorithm for scheduling acyclic job-shop can guarantee a better worst-case performance than . We consider two special cases of the acyclic job-shop with the so-called short jobs and short operations (restricting the maximal job and operation length) and solve them optimally in linear time. We show that scheduling m identical processors with at most m−2 preemptions is NP-hard, whereas a venerable early linear-time algorithm by McNaughton yields m−1 preemptions. Another multiprocessor scheduling problem we consider is that of scheduling m unrelated processors with an additional restriction that the processing time of any job on any machine is no more than the optimal schedule makespan C _max^*. We show that the (2m−3)-preemptive version of this problem is polynomially solvable, whereas the (2m−4)-preemptive version becomes NP-hard. For general unrelated processors, we guarantee near-optimal (2m−3)-preemptive schedules. The makespan of such a schedule is no more than either the corresponding non-preemptive schedule makespan or max {C _max^*,p _max}, where C _max^* is the optimal (preemptive) schedule makespan and p _max is the maximal job processing time. E.V. Shchepin was partially supported by the program “Algebraical and combinatorial methods of mathematical cybernetics” of the Russian Academy of Sciences. N. Vakhania was partially supported by CONACyT grant No. 48433.     

Complexity of shop-scheduling problems with fixed number of jobs: a survey

The paper surveys the complexity results for job shop, flow shop, open shop and mixed shop scheduling problems when the number n of jobs is fixed while the number r of operations per job is not restricted. In such cases, the asymptotical complexity of scheduling algorithms depends on the number m of machines for a flow shop and an open shop problem, and on the numbers m and r for a job shop problem. It is shown that almost all shop-scheduling problems with two jobs can be solved in polynomial time for any regular criterion, while those with three jobs are NP-hard. The only exceptions are the two-job, m-machine mixed shop problem without operation preemptions (which is NP-hard for any non-trivial regular criterion) and the n-job, m-machine open shop problem with allowed operation preemptions (which is polynomially solvable for minimizing makespan).     

Preemptive scheduling with rejection

 We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly -hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection. Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002 Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084 Supported by the START program Y43-MAT of the Austrian Ministry of Science.     

Improved Bounds for Acyclic Job Shop Scheduling

In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations). Received June 30, 1998 RID="*" ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair RID="†" ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation.     

All-norm approximation algorithms

A major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. In many cases the various measures are different ℓ_p norms. We address this problem by introducing the concept of an all-norm ρ-approximation algorithm, which supplies one solution that guarantees ρ-approximation to all ℓ_p norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are m machines and n jobs, each job is associated with a subset of the machines and should be assigned to one of them. Previous work considered approximation algorithms for each norm separately. Lenstra et al. [Math. Program. 46 (1990) 259–271] showed a 2-approximation algorithm for the problem with respect to the ℓ_∞ norm. For any fixed ℓ_p norm the previously known approximation algorithm has a performance of θ(p). We provide an all-norm 2-approximation polynomial algorithm for the restricted assignment problem. On the other hand, we show that for any given ℓ_p norm (p>1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given ℓ_p norm a FPTAS for any fixed number of machines.     

An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines

We give a new and efficient approximation algorithm for scheduling precedence-constrained jobs on machines with different speeds. The problem is as follows. We are given n jobs to be scheduled on a set of m machines. Jobs have processing times and machines have speeds. It takes p_j/s_i units of time for machine i with speed s_i to process job j with processing requirement p_j. Precedence constraints between jobs are given in the form of a partial order. If j k, processing of job k cannot start until job j's execution is completed. The objective is to find a non-preemptive schedule to minimize the makespan of the schedule. Chudak and Shmoys (1997, “Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),” pp. 581–590) gave an algorithm with an approximation ratio of O(log m), significantly improving the earlier ratio of due to Jaffe (1980, Theoret. Comput. Sci.26, 1–17). Their algorithm is based on solving a linear programming relaxation. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n³) time. Our algorithm is based on a new and simple lower bound which we believe is of independent interest.     

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)     

Performance of scheduling algorithms for no-wait flowshops with parallel machines

We study the performance of scheduling algorithms for a manufacturing system, called the ‘no-wait flowshop’, which consists of a certain number of machine centers. Each center has one or more identical parallel machines. Each job is processed by at most one machine in each center. The problem of finding the minimum finish time schedule is considered here in a flowshop consisting of two machine centers. Heuristic algorithms are presented and are analyzed in the worst case performance context. For the case of two centers, one with a single machine and the other with m, two heuristics are presented with tight performance guarantees of 3 − (1/m) and 2. When both centers have m machines, a heuristic is presented with an upper bound performance guarantee of . It is also shown that this bound can be reduced to 2(1 + ε). For the flowshop with any number of machines in each center, we provide a heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers.     

Optimal scheduling on parallel machines for a new order class

This paper addresses the problem of scheduling n unit length tasks on m identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on any number of machines.     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.     

Online makespan minimization in MapReduce-like systems with complex reduce tasks

In the MapReduce processing, since map tasks output key-value pairs, and reduce tasks take the pairs output by the map tasks and compute the final results. Therefore, reduce tasks are unknown until their map tasks are finished. Also, we assume that map tasks are preemptive and parallelizable, but reduce tasks are non-parallelizable. With these assumptions, we study the scheduling of minimizing makespan. Both preemptive and non-preemptive reduce tasks are considered. We prove that no matter if preemption is allowed or not, any algorithm has a competitive ratio at least \(2-\frac{1}{h}\), we then give two optimal algorithms for these two versions.     

Optimal on-line flow time with resource augmentation

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has ? machines. We design an algorithm of competitive ratio , where Δ is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant ?. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only Δ and n are known. This gives a trade-off between the resource augmentation and the competitive ratio.We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has ?m machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time.     

A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines

We study the problem of scheduling n non-preemptive jobs on m unrelated parallel machines. Each machine can process a specified subset of the jobs. If a job is assigned to a machine, then it occupies a specified time interval on the machine. Each assignment of a job to a machine yields a value. The objective is to find a subset of the jobs and their feasible assignments to the machines such that the total value is maximized. The problem is NP-hard in the strong sense. We reduce the problem to finding a maximum weight clique in a graph and survey available solution methods. Furthermore, based on the peculiar properties of graphs, we propose an exact solution algorithm and five heuristics. We conduct computer experiments to assess the performance of our and other existing heuristics. The computational results show that our heuristics outperform the existing heuristics.     

Local search algorithms for the multiprocessor flow shop scheduling problem

The multiprocessor flow shop scheduling problem is a generalization of the ordinary flow shop scheduling problem. The problem consists of both assigning operations to machines and scheduling the operations assigned to the same machine. We review the literature on local search methods for flow shop and job shop scheduling and adapt them to the multiprocessor flow shop scheduling problem. Other local search approaches we consider are variable-depth search and simulated annealing. We show that tabu search and variable-depth search with a neighborhood originated by Nowicki and Smutnicki outperform the other algorithms.     

Preemptive scheduling of two uniform parallel machines to minimize total tardiness

We consider the problem of preemptive scheduling n jobs on two uniform parallel machines. All jobs have equal processing requirements. For each job we are given its due date. The objective is to find a schedule minimizing total tardiness ∑T_i. We suggest an O(n log n) algorithm to solve this problem.     

Scheduling unit — time tasks on flow — shops under resource constraints

We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is proved that when the number of machines is arbitrary, the problem of minimizing schedule length is NP-hard, even when only one unit of the additional resource is available in the system. On the other hand, when the number of machines is fixed, then the problem is solvable in polynomial time, even for an arbitrary number of resource units available. For the two machine case anO(n log ₂ ² n) algorithm minimizing maximum lateness is also given. The presented results are also of importance in some message transmission systems.     

Open shop problems with unit time operations

We show that them-machine open shop problem in which all operations have unit processing times can be polynomially transformed to a special preemptive scheduling problem onm identical parallel machines. Many results published recently as well as some new results are derived by using this transformation. The new results include solutions of open problems mentioned in a recent paper by Kubiak et al. p]A similar relationship is derived between no-wait open shop problems with unit time operations andm-machine problems with jobs having unit processing times.This work was supported by Deutsche Forschungsgemeinschaft (Project JoPTAG).     

Rational preemptive scheduling

In scheduling jobs subject to precedence constraints that form a partial order, it is advantageous to interrupt (preempt) jobs, and return to complete them at a later time in order to minimize total completion time. It is clearly desirable to see that such preemptive scheduling by finitely many machines requires only intervals of work, and not a more general assignment of tasks over measurable sets, for optimal completion. It is a deeper fact that arbitrarily small intervals are required for a fixed number of machines m>-3 for optimal preemptive scheduling. On the other hand, if the number of jobs is fixed, say n, then it is intuitively clear that it suffices to use only comparatively large intervals (but less clear how large will suffice!). The authors address these and certain related questions.     

Scheduling jobs with time-resource tradeoff via nonlinear programming

We consider a scheduling problem where the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The objective is to find a resource allocation and a schedule that minimizes the makespan. We explicitly allow for succinctly encodable time-resource tradeoff functions, which calls for mathematical programming techniques other than those that have been used before. Utilizing a (nonlinear) integer mathematical program, we obtain the first polynomial time approximation algorithm for the scheduling problem, with performance bound (3+ε) for any ε>0. Our approach relies on a fully polynomial time approximation scheme to solve the nonlinear mathematical programming relaxation. We also derive lower bounds for the approximation.