Optimal task sequencing with precedence constraints

A given finite set of tasks, having known nonnegligible failure probabilities and known costs (or rewards) for their performance, can be performed sequentially until either one of the tasks fails or all tasks have been executed. The allowable task performance sequences are constrained only by certain precedence requirements, which specify that certain tasks must be performed before certain other tasks. Given the individual task failure probabilities and task costs, along with the intertask precedence requirements, the problem is to determine an optimal task performance sequence having minimal expected cost (or maximal expected reward). A number of potential applications of such “task ordering” problems are described, including R&D project organization, design of screening procedures, and determining testing points for sequential manufacturing processes.The main results of this paper are a number of reduction theorems which lead to a very efficient optimization algorithm for a large class of task ordering problems. Though these theorems are not quite sufficient for us to give a fast optimization algorithm, we do show how their use can improve upon exhaustive search techniques.     

Reduction of job-shop problems to flow-shop problems with precedence constraints

We study the problem of scheduling N independent jobs in a job-shop environment. Each job must be processed on M machines according to individual routes. The objective is to minimize the maximum completion time of the jobs. First, the job-shop problem is reduced to a flow-shop problem with job precedence constraints. Then, a set of flow-shop algorithms are modified to solve it. To evaluate the quality of these heuristics, several lower bounds on the optimal solution have been computed and compared with the heuristic solutions for 3040 problems. The heuristics appear especially promising for job-shop problems with ‘flow-like’ properties.     

Schedule execution for two-machine flow-shop with interval processing times

This paper addresses the issue of how to best execute the schedule in a two-phase scheduling decision framework by considering a two-machine flow-shop scheduling problem in which each uncertain processing time of a job on a machine may take any value between a lower and upper bound. The scheduling objective is to minimize the makespan. There are two phases in the scheduling process: the off-line phase (the schedule planning phase) and the on-line phase (the schedule execution phase). The information of the lower and upper bound for each uncertain processing time is available at the beginning of the off-line phase while the local information on the realization (the actual value) of each uncertain processing time is available once the corresponding operation (of a job on a machine) is completed. In the off-line phase, a scheduler prepares a minimal set of dominant schedules, which is derived based on a set of sufficient conditions for schedule domination that we develop in this paper. This set of dominant schedules enables a scheduler to quickly make an on-line scheduling decision whenever additional local information on realization of an uncertain processing time is available. This set of dominant schedules can also optimally cover all feasible realizations of the uncertain processing times in the sense that for any feasible realizations of the uncertain processing times there exists at least one schedule in this dominant set which is optimal. Our approach enables a scheduler to best execute a schedule and may end up with executing the schedule optimally in many instances according to our extensive computational experiments which are based on randomly generated data up to 1000 jobs. The algorithm for testing the set of sufficient conditions of schedule domination is not only theoretically appealing (i.e., polynomial in the number of jobs) but also empirically fast, as our extensive computational experiments indicate.     

On the complexity of dynamic programming for sequencing problems with precedence constraints

Dynamic programming has been successfully used in the past to solve a large class of precedence constrained sequencing problems including for example, the assembly line balancing problem and the total tardiness problem on a single machine. The main limitation of this method has been the amount of storage required, which is directly related to the number of ideals in the precedence structure. In this paper, we present classes for which this number can be efficiently computed, enabling us to decide, in advance, whether the storage requirements of dynamic programming would be excessive for the problem. We develop regression equations based on large-scale computational experiments, which lead to surprisingly good approximations for the number of ideals. We also report on a computational study, comparing the relative effectiveness of various implementations of dynamic programming. A common theme throughout the paper is that the width of the precedence constraints plays the most important role in determining the storage requirements of dynamic programming for a sequencing problem.The author gratefully acknowledges the Editor and two anonymous referees, whose suggestions led to an improved version of the paper. This research was supported in part by the National Sciences and Engineering Research Council of Canada under Grant No. A1798.     

Minimising makespan in the two-machine flow-shop with release times

This paper considers the two-machine flow-shop problem with the objective of minimising the makespan subject to different release times. In view of the strongly NP-hard nature of this problem, five lower bounds and two new dominance criteria are proposed together with a decomposition procedure that reduces the problem size by setting jobs at the beginning of the sequence. Several branch and bound procedures are described by applying different lower bounds and branching schemes. A detailed computational campaign has been performed on different kinds of instances testing problems with size up to 200 jobs.     

Sequencing with general precedence constraints

Consider a set of jobs where an arbitrary precedence relationship exists among the jobs and a cost is associated with every permutation of the jobs. The objective is to find a minimum-cost permutation which is consistent with the precedence relations. A class of problems is studied which includes the least-cost fault detection problem, the one-machine total weighted completion time problem, and the two-machine maximum flow-time problem.Transformations are developed which systematically reduce the size of the general precedence-constrained problem. This process continues until either the problem is solved or no further reductions are possible. The worst-case effectiveness of these transformations is analyzed in detail. These results generalize the majority of work previously done on efficient sequencing with precedence constraints.     

The bounded core for games with precedence constraints

An element of the possibly unbounded core of a cooperative game with precedence constraints belongs to its bounded core if any transfer to a player from any of her subordinates results in payoffs outside the core. The bounded core is the union of all bounded faces of the core, it is nonempty if the core is nonempty, and it is a continuous correspondence on games with coinciding precedence constraints. If the precedence constraints generate a connected hierarchy, then the core is always nonempty. It is shown that the bounded core is axiomatized similarly to the core for classical cooperative games, namely by boundedness (BOUND), nonemptiness for zero-inessential two-person games (ZIG), anonymity, covariance under strategic equivalence (COV), and certain variants of the reduced game property (RGP), the converse reduced game property (CRGP), and the reconfirmation property. The core is the maximum solution that satisfies a suitably weakened version of BOUND together with the remaining axioms. For games with connected hierarchies, the bounded core is axiomatized by BOUND, ZIG, COV, and some variants of RGP and CRGP, whereas the core is the maximum solution that satisfies the weakened version of BOUND, COV, and the variants of RGP and CRGP.     

Heuristics for unrelated machine scheduling with precedence constraints

In this paper, we consider the problem of scheduling tasks on unrelated parallel machines. Precedence constraints between the tasks form chains of tasks. We propose a number of heuristics in order to find near optimal solutions to the problem. Empirical results show that the heuristics are able to find very good approximate solutions.     

A monotone approximation algorithm for scheduling with precedence constraints

We provide a monotone O(m^2/3)-approximation algorithm for scheduling related machines with precedence constraints.     

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.     

The two-machine flow-shop problem with weighted late work criterion and common due date

The paper is on the two-machine non-preemptive flow-shop scheduling problem with a total weighted late work criterion and a common due date (F2|d_i=d|Y_w). The late work performance measure estimates the quality of the obtained solution with regard to the duration of late parts of tasks not taking into account the quantity of this delay. We prove the binary NP-hardness of the problem mentioned by showing a transformation from the partition problem to its decision counterpart. Then, a dynamic programming approach of pseudo-polynomial time complexity is formulated.     

Approximability of two-machine no-wait flowshop scheduling with availability constraints

We consider in this paper the two-machine no-wait flowshop scheduling problem in which each machine may have an unavailable interval. We present a polynomial time approximation scheme for the problem when the unavailable interval is imposed on only one machine, or the unavailable intervals on the two machines overlap.     

Parallel dedicated machines scheduling with chain precedence constraints

A set of n nonpreemptive tasks are to be scheduled on m parallel dedicated machines with a regular criterion. Chain precedence constraints among the tasks, deterministic processing times and processing machine of each task are given.     

Discovering implied constraints in precedence graphs with alternatives

During automated problem solving it may happen that some knowledge that is known at the user level is lost in the formal model. As this knowledge might be important for efficient problem solving, it seems useful to re-discover it in order to improve the efficiency of the solving procedure. This paper compares three methods for discovering certain implied constraints in the constraint models describing manufacturing (and other) processes with serial, parallel, and alternative operations. In particular, we focus on identifying equivalent nodes in the precedence graph with parallel and alternative branches. Equivalent nodes correspond to operations that either must be all simultaneously present or none of them can be present in the schedule. Such information is frequently known at the user level, but it is lost in the formal model. The paper shows that identifying equivalent nodes is an NP-hard problem in general, but it is tractable if the graph has a nested structure. As the nested structure is typical for real-life processes and workflows, we use the nested graphs to experimentally compare the proposed methods.     

An improved monotone algorithm for scheduling related machines with precedence constraints

We answer an open question posed by Krumke et al. (2008) [6] by showing how to turn the algorithm of Chekuri and Bender for scheduling related machines with precedence constraints into an O(logm)-approximation algorithm that is monotone in expectation. This significantly improves on the previously best known monotone approximation algorithms for this problem, from Krumke et al. [6] and Thielen and Krumke (2008) [8], which have an approximation guarantee of O(m^2/3).     

The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: lower and upper bounds for the random processing time are given before scheduling, but its probability distribution between these bounds is unknown. For such a problem, there often does not exist a dominant schedule that remains optimal for all possible realizations of the job processing times, and we look for a minimal set of schedules that is dominant. Such a minimal dominant set of schedules may be represented by a dominance digraph. We investigate useful properties of such a digraph.     

Algorithms for optimization problems with exclusion constraints

This paper proposes algorithms for minimizing a continuously differentiable functionf(x): ⁿ subject to the constraint thatx does not lie in specified bounded subsets of ⁿ . Such problems arise in a variety of applications, such as tolerance design of electronic circuits and obstacle avoidance in the selection of trajectories for robot arms. Such constraints have the form . The function is not continuously differentiable. Algorithms based on the use of generalized gradients have considerable disadvantages because of the local concavity of at points where the set {j|g ^j (x)=(x)} has more than one element. Algorithms which avoid these disadvantrages are presented, and their convergence is established.This research was sponsored in part by the National Science Foundation under Grant ECS-81-21149, the Air Force Office of Scientific Research (AFSC), United States Air Force under Contract F49620-79-C-0178, the Office of Naval Research under Grant N00014-83-K-0602, the Air Force Office of Scientific Research under Grant AFOSR-83-0361, and the Semiconductor Research Consortium under Grant SRC-82-11-008.