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.     

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.     

New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints

We propose a new formulation for the asymmetric traveling salesman problem, with and without precedence relationships, which employs a polynomial number of subtour elimination constraints that imply an exponential subset of certain relaxed Dantzig-Fulkerson-Johnson subtour constraints. Promising computational results are presented, particularly in the presence of precedence constraints.     

The bipartite margin shop and maximum red matchings free of blue–red alternating cycles

The margin shop arises as a model of margining investment portfolios in a batch, a mandatory end-of-day risk management operation for any prime brokerage firm. The margin-shop scheduling problem is the extension of the preemptive flow-shop scheduling problem where precedence constraints can be introduced between preempted parts of jobs. This paper is devoted to the bipartite case which is equivalent to the problem of finding a maximum red matching that is free of blue–red alternating cycles in a complete bipartite graph with blue and red edges. It is also equivalent to the version of the jump-number problem for bipartite posets where jumps inside only one part should be counted. We show that the unit-time bipartite margin-shop scheduling problem is NP-hard but can be solved in polynomial time if the precedence graph is of degree at most two or a forest.     

Balancing U-lines in a multiple U-line facility

U-shaped production lines and facilities consisting of many such lines are important parts of modem manufacturing systems. The problem of balancing and rebalancing U-line facilities is studied in this paper. Like the traditional line balancing problem this problem is NP-hard. The objective is to assign tasks to a minimum number of regular, crossover, and multiline stations while satisfying cycle time, precedence, location, and station-type constraints. A secondary objective is to concentrate the idle time in one station so that improvement efforts can be focused there in accordance with modern just-in-time principles. A reaching dynamic programming algorithm is presented for determining optimal balances. It is effective for balancing and rebalancing facilities with any number of U-lines, provided that individual U-lines do not have more than 22 tasks and do not have wide, sparse precedence graphs.     

On the representation of the one machine sequencing problem in the shifting bottleneck heuristic

The Shifting Bottleneck heuristic decomposes the Job Shop problem into a series of One Machine Sequencing Problems (OMSPs) with release and due dates, precedence constraints and the minimization of maximum lateness objective. It is well known that delayed precedence constraints may exist between two operations to be performed on the same machine. We identify a new type of precedence relationship that may exist in an OMSP between the predecessor of an operation and the successor of another. The premise that an OMSP captures the sequencing relationships on other machines in the release and due date information is not valid when such precedence relationships exist. A modification of the OMSP representation is proposed based on a generalized lateness objective defined on a due window. The implications of such a representation for the OMSP solution procedure have been explored.     

Preemptive Hybrid Flowshop Scheduling problem of interval orders

The Preemptive Hybrid (multi-processor) Flowshop Scheduling (PHFS) problem consists in preemptively scheduling n jobs in a flowshop subject to precedence constraints with the objective of minimizing the makespan. A special case of the general precedence constraints problems is NP-hard in the strong sense, Hoogeveen et al. [J.A. Hoogeveen, J.K. Lenstra, B. Veltman, European Journal of Operational Research 89 (1996) 172]. In this paper a class of precedence constraints is proposed for which the problem is polynomially solvable. The reported results demonstrate the feasibility and reliability of the proposed approach. This should open future prospects for developing approximation algorithms for any class of precedence constraints.     

极小化最大提前完工费用的可中断排序问题

讨论了带截止期限的$n$个工件在单机上加工,工件间存在优先约束,在允许机器空闲的条件下,确定一个工件的可中断排序,极小化最大提前完工费用.首先考虑两种特殊情形:(1)截止期限相同,存在优先约束;(2)截止期限任意,不存在优先约束.针对两种情形分别给出了时间复杂度为$O(n^2)$的算法.在此基础上,考虑普遍情形,即截止期限任意,存在优先约束,也给出了一个时间复杂度为$O(n^2)$的算法.由于工件不允许延迟,问题可能会无可行排序,需先对问题的可行性进行讨论.     

A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints

This study concerns the domain of cyclic scheduling. More precisely we consider the cyclic job shop scheduling problem with linear constraints. The main characteristic of this problem is that the tasks of each job are cyclic and are subjected to linear precedence constraints. First we review some approaches in the field of cyclic scheduling and present the cyclic job shop scheduling problem definition, which has an open complexity. Then we present a general approach for solving it, based on the coupling of a genetic algorithm and a scheduler. This scheduler utilises a Petri-net modelling the linear precedence constraints between cyclic tasks. The goal of this genetic algorithm is to propose an order of priority for jobs on the machines, to be used by the scheduler for solving resource conflicts. Finally a benchmark and some preliminary results of this approach are presented.     

Precedence theorems and dynamic programming for the single-machine weighted tardiness problem

We tackle precedence-constrained sequencing on a single machine in order to minimize total weighted tardiness. Classic dynamic programming (DP) methods for this problem are limited in performance due to excessive memory requirements, particularly when the precedence network is not sufficiently dense. Over the last decades, a number of precedence theorems have been proposed, which distinguish dominant precedence constraints for a job pool that is initially without precedence relation. In this paper, we connect and extend the findings of the foregoing two strands of literature. We develop a framework for applying the precedence theorems to the precedence-constrained problem to tighten the search space, and we propose an exact DP algorithm that utilizes a new efficient memory management technique. Our procedure outperforms the state-of-the-art algorithm for instances with medium to high network density. We also empirically verify the computational gain of using different sets of precedence theorems.     

Scheduling groups of tasks with precedence constraints on three dedicated processors

We study the problem of scheduling groups of tasks with precedence constraints on three dedicated processors. Each task requires a specified set of processors. Up to three precedence constraints are considered among groups of tasks requiring the same set of processors. The objective of the problem is to find a nonpreemptive schedule which minimizes the maximum completion time (makespan). This scheduling problem is equivalent to the problem of finding an extension of the constraint graph (i.e. the graph which represents the conflicts between tasks and the precedence constraints) to a comparability graph with minimum (over all the extensions) maximum clique weight. The problem is NP-hard in the strong sense. A normal schedule is such that all the tasks requiring the same set of processors are scheduled consecutively. With a normal schedule the problem reduces to the quotient graph of the constraint graph. In this paper we obtain tight approximation results for the minimum makespan of a normal schedule through tight results on the minimum increase of the maximum clique weight when the (partially oriented) quotient graph is extended to a comparability graph.     

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.     

Solving a gas-lift optimization problem by dynamic programming

Gas lift is a costly, however indispensable means to recover oil from high-depth reservoirs that entails solving the gas-lift optimization problem, GOP, often in response to variations in the dynamics of the reservoir and economic oscillations. GOP can be cast as a mixed integer nonlinear programming problem whose integer variables decide which oil wells should produce, while the continuous variables allocate the gas-compressing capacity to the active ones. This paper extends the GOP formulation to encompass uncertainties in the oil outflow and precedence constraints imposed on the activation of wells. Recursive solutions are suggested for instances devoid of precedence constraints, as well as instances arising from precedence constraints induced by forests and general acyclic graphs. For the first two classes, pseudo-polynomial algorithms are developed to solve a discretized version of GOP, while the most general version is shown to be NP-Hard in the strong sense. Numerical experiments provide evidence that the approximate algorithms obtained by solving the recurrences produce near-optimal solutions. Further, the family of cover inequalities of the knapsack problem is extended to the gas-lift optimization problem.     

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).     

On the complexity of project scheduling to minimize exposed time

We consider project scheduling where the project manager’s objective is to minimize the time from when an adversary discovers the project until the completion of the project. We analyze the complexity of the problem identifying both polynomially solvable and NP-hard versions of the problem. The complexity of the problem is seen to be dependent on the nature of renewable resource constraints, precedence constraints, and the ability to crash activities in the project.     

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.     

Iteration method in a routing problem with internal losses

The problem of a sequential traversal of sets is considered, which is complicated by the necessity of fulfilling (internal) tasks on the sets as well as by constraints in the form of precedence conditions. It is assumed that the method of aggregating the expenses is additive. For the appearing extremal problem with dependent variables, an equivalent transformation to an optimization problem on a Cartesian product is proposed. Based on this, an iteration method is constructed that uses a reconstructible model of the courier problem (a traveling salesman problem complicated by precedence conditions).     

Scheduling unit-length jobs with precedence constraints of small height

We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.     

Maximization Problems in Single Machine Scheduling

Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n?1 jobs available at the same time. It is solved in O(mn+n ²) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n?1 jobs available at the same time.     

The precedence-constrained asymmetric traveling salesman polytope

Many applications of the traveling salesman problem require the introduction of additional constraints. One of the most frequently occurring classes of such constraints are those requiring that certain cities be visited before others (precedence constraints). In this paper we study the Precedence-Constrained Asymmetric Traveling Salesman (PCATS) polytope, i.e. the convex hull of incidence vectors of tours in a precedence-constrained directed graph. We derive several families of valid inequalities, and give polynomial time separation algorithms for important subfamilies. We then establish the dimension of the PCATS polytope and show that, under reasonable assumptions, the two main classes of inequalities derived are facet inducing.An early version of this paper was presented at the Oberwolfach Conference on Combinatorial Optimization in January 1991. This research was supported in part by the National Science Foundation, Grant #DDM-8901495 and the Office of Naval Research through Contract N00014-85-K-0198.Corresponding author.The work of this author was supported by MURST, Italy.