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.     

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.     

A 3/2-Approximation for the proportionate two-machine flow shop scheduling with minimum delays

We study the two-machine flow shop problem with minimum delays. The problem is known to be strongly NP-hard even in the case of unit processing times and to be approximable within a factor of 2 of the length of an optimal schedule in the general case. The question whether there exists a polynomial-time algorithm with a better approximation ratio has been posed by several researchers but still remains open. In this paper, we improve the above bound to 3/2 for the special case of the problem when both operations of each job have equal processing times (this case of flow shop is known as the proportionate flow shop). Our analysis of the algorithm relies upon a nontrivial generalization of the lower bound established by W. Yu for the case of unit processing times.     

Some properties of optimal schedules for the Johnson problem with preemption

The properties are under study of the optimal schedules for the NP-hard Johnson problem with preemption. The length of an optimal schedule is shown to coincide with the total length of some subset of operations. These properties demonstrate that the optimal schedule of every instance of the problem can be found by a greedy algorithm (for the properly defined priority orders of operations on machines). This yields the first exact algorithm for the problem known since 1978. It is shown that the number of interruptions in a greedy schedule (and therefore, in the optimal schedule) is at most the number of operations, which is significantly better than the available upper bounds on the number of interruptions in the optimal schedule.     

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.     

Approximating Scheduling Unrelated Parallel Machines in Parallel

We show how to approximate in NC the problem of scheduling unrelated parallel machines, for a fixed number of machines in which the makespan C _max is the objective function to minimize. We develop an approximate NC algorithm which finds a schedule whose length is at most (1+o(1))(C^* _max + 3 C^* _maxln(2n(n-1)/)), where C*_max denotes the optimal schedule, n the total number of jobs and a small positive constant. Our approach shows how to relate the linear program obtained by relaxing the integer programming formulation of the problem with a linear program formulation that is positive and in the packing/covering form. The established relationship enables us to transfer approximate fractional solutions from the later formulation that is known to be approximable in NC. Then, we show how to obtain an integer approximate solution, i.e. a schedule, from the fractional one, using the randomized rounding technique. We stress that our analysis assumes that the length of the schedule is (ln n) and that the min p _ij and max p _ij values are not too disparate (where p _ij is the time to run job j on machine i).Finally, we show that the same technique can be applied to the general assignment problem with a fixed number of machines and makespan T.     

Complexity Results for Flow-Shop and Open-Shop Scheduling Problems with Transportation Delays

We consider shop problems with transportation delays where not only the jobs on the machines have to be scheduled, but also transportation of the jobs between the machines has to be taken into account. Jobs consisting of a given number of operations have to be processed on machines in such a way that each machine processes at most one operation at a time and a job is not processed by more than one machine simultaneously. Transportation delays occur if a job changes from one machine to another. The objective is to find a feasible schedule which minimizes some objective function. A survey of known complexity results for flow-shop and open-shop environments is given and some new complexity results are derived.     

最后完工机器至多两个空闲的自由作业稠密时间表(英文)

对于自由作业问题,在安排工件时避免不必要空闲所得的时间表称为稠密时间表.稠密时间表的加工总长不超过最优值的2-1/m倍,是一个在机器数m6时尚未被证明的猜想.本文通过引入工件与机器特征函数及机器关于工件非间断等概念,研究当最后完工机器至多有两个空闲区间时,性能比猜想成立的充分条件.     

Single machine scheduling subject to precedence delays

A single-machine scheduling problem with precedence delays is analyzed. A set of n tasks is to be scheduled on the machine in such a way that the makespan is minimized. The executions of the tasks are constrained by precedence delays, i.e., a task can start its execution only after any of its predecessors has completed and the delay between the two tasks has elapsed. In the case of unit execution times and integer lengths of delays, the problem is shown to be NP-hard in the strong sense. In the case of integer execution times and unit length of delays, the problem is polynomial, and an O(n²) optimal algorithm is provided. Both preemptive and non-preemptive cases are considered.     

On the complexity of scheduling unrelated parallel machines with limited preemptions

We consider the problem of finding a minimum-length preemptive schedule for n jobs on m parallel machines. The problem is solvable in polynomial time, whether the machines are identical, uniform or unrelated. For identical or uniform machines, it is easy to obtain an optimal schedule in which the portion of a job that is assigned to a single machine is processed without interruption. We show that imposing this condition in the case of unrelated machines makes the problem NP-hard.     

Approximating schedules for dynamic process graphs efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.

In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.

In this paper we study a subclass of dynamic process graphs called -output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is -complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a -complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion.     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

Flow-based formulations for operational fixed interval scheduling problems with random delays

We deal with operational fixed interval scheduling problem with random delays in job processing times. We formulate two stochastic programming problems. In the first problem with a probabilistic objective, all jobs are processed on available machines and the goal is to obtain a schedule with the highest attainable reliability. The second problem is to select a subset of jobs with the highest reward under a chance constraint ensuring feasibility of the schedule with a prescribed probability. We assume that the multivariate distribution of delays follows an Archimedean copula, whereas there are no restrictions on marginal distributions. We introduce new deterministic integer linear reformulations based on flow problems. We compare the formulations with the extended robust coloring problem, which was shown to be a deterministic equivalent to the stochastic programming problem with probabilistic objective by Branda et al. (Comput Ind Eng 93:45–54, 2016). In the numerical study, we report average computational times necessary to solve a large number of simulated instances. It turns out that the new flow-based formulation helps to solve the FIS problems considerably faster than the other one.     

On the complexity of scheduling with large communication delays

Given a directed acyclic graph (dag) with unit execution time tasks and constant communication delays c ⩾ 2, we are interested in deciding if there is a schedule for the dag of length at most L. We prove that the problem is polynomial when L is equal to (c + 1), or (c + 2) for the special case of c = 2, and that it is NP-complete for (c + 3) for any value of c, even in the case of a bipartite dag of depth one.     

A polynomial algorithm for a two-machine no-wait job-shop scheduling problem

This paper considers the no-wait scheduling of n jobs, where each job is a chain of unit processing time operations to be processed alternately on two machines. The objective is to minimize the mean flow time. We propose an O(n⁶)-time algorithm to produce an optimal schedule. It is also shown that if zero processing time operations are allowed, then the problem is NP-hard in the strong sense.     

Optimality of monotonic policies for two-action Markovian decision processes,with applications to control of queues with delayed information

We consider a discrete-time Markov decision process with a partially ordered state space and two feasible control actions in each state. Our goal is to find general conditions, which are satisfied in a broad class of applications to control of queues, under which an optimal control policy is monotonic. An advantage of our approach is that it easily extends to problems with both information and action delays, which are common in applications to high-speed communication networks, among others. The transition probabilities are stochastically monotone and the one-stage reward submodular. We further assume that transitions from different states are coupled, in the sense that the state after a transition is distributed as a deterministic function of the current state and two random variables, one of which is controllable and the other uncontrollable. Finally, we make a monotonicity assumption about the sample-path effect of a pairwise switch of the actions in consecutive stages. Using induction on the horizon length, we demonstrate that optimal policies for the finite- and infinite-horizon discounted problems are monotonic. We apply these results to a single queueing facility with control of arrivals and/or services, under very general conditions. In this case, our results imply that an optimal control policy has threshold form. Finally, we show how monotonicity of an optimal policy extends in a natural way to problems with information and/or action delay, including delays of more than one time unit. Specifically, we show that, if a problem without delay satisfies our sufficient conditions for monotonicity of an optimal policy, then the same problem with information and/or action delay also has monotonic (e.g., threshold) optimal policies.     

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.     

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.     

On-line scheduling of small open shops

We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.     

Coordination mechanisms with hybrid local policies

We study coordination mechanisms for scheduling n jobs on m parallel machines where agents representing the jobs interact to generate a schedule. Each agent acts selfishly to minimize the completion time of his/her own job, without considering the overall system performance that is measured by a central objective. The performance deterioration due to the lack of a central coordination, the so-called price of anarchy, is determined by the maximum ratio of the central objective function value of an equilibrium schedule divided by the optimal value. In the first part of the paper, we consider a mixed local policy with some machines using the SPT rule and other machines using the LPT rule. We obtain the exact price of anarchy for the problem of minimizing the makespan and some bounds for the problem of minimizing the total completion time. In the second part of the paper, we consider parallel machine scheduling subject to eligibility constraints. We devise new local policies based on the flexibilities and the processing times of the jobs. We show that the newly devised local policies outperform both the SPT and the LPT rules.