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.     

Scheduling tasks on a flexible manufacturing machine to minimize tool change delays

This paper considers the problem of scheduling a given set of precedence constraint tasks on a flexible machine equipped with a tool magazine where each task requires exactly one of the tools during its execution. Changing from one tool to another requires a certain amount of time that depends on the pair of tools being exchanged. We present a new algorithmic approach for general task precedence relations when it is desired to sequence the tasks in such a way that the total time required for tool changes is minimized. The proposed algorithm is of polynomial time complexity in case of task precedences of limited width w, i.e. for precedence relations where each subset of independent tasks has not more than w elements. Since the task precedences width w could be arbitrary, we describe two heuristic algorithms and empirically evaluate their effectiveness in finding schedules with minimum total time required for tool changes.     

‘Strong’-‘weak’ precedence in scheduling: Extensions to series-parallel orders

We examine computational complexity implications for scheduling problems with job precedence relations with respect to strong precedence versus weak precedence. We propose a consistent definition of strong precedence for chains, trees, and series-parallel orders. Using modular decomposition for partially ordered sets (posets), we restate and extend past complexity results for chains and trees as summarized in Dror (1997) [5]. Moreover, for series-parallel posets we establish new computational complexity results for strong precedence constraints for single- and multi-machine problems.     

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.     

On scheduling with the non-idling constraint

In this paper, we give an overview of the main results obtained on the complexity of scheduling under the non-idling constraint, i.e, when the jobs assigned to each machine must be processed with no intermediate delay. That constraint is met in practice when the cost of intermediate idle time is too high due to the idle time itself and/or the machine restarting. The non idling constraint is a strong constraint that often needs a new solving approach and most results about classical scheduling problems do not easily extend to the non-idling variant of the problem. In this survey, we mainly consider the non-idling variants of the basic scheduling problems. So, we first present basic properties, complexity results and some algorithms concerning the one-machine non-idling scheduling problem. Then we consider the $m$ -machine non idling scheduling problem. We show that a few basic problems may be solved by rather easy extensions of the algorithm solving their classical counterpart. However, the complexity status of the non idling version of quite easy polynomial basic problems remains an open question. We finally consider a more constrained version of non-idling, called the “homogeneously non idling” constraint, where for any subset of machines, the union of their busy intervals must make an interval and we present the structural property that leads to a polynomial algorithm for unit time jobs and a weak precedence. We conclude by giving some research directions that seem quite interesting to study both for theoretical and practical issues.     

Computational complexity of some scheduling problems with multiprocessor tasks

The paper is concerned with scheduling problems with multiprocessor tasks and presents conditions under which such problems can be solved in polynomial time. The application of these conditions is illustrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem with a UET task system, two parallel processors, the criterion of total completion time, and precedence constraints in the form of out-trees.     

Stochastic lot-sizing with backlogging: computational complexity analysis

For a multi-stage stochastic programming problem, one approach is to explore a scenario tree based formulation for the problem and solve the formulation efficiently. There has been significant research progress on how to generate scenario trees in the literature. However, there is limited work on analyzing the computational complexity of the scenario-tree based formulation that considers the number of tree nodes as the input size. In this paper, we use stochastic lot-sizing problems as examples to study the computational complexity issues for the scenario-tree based formulations. We develop production path properties and a general dynamic programming framework based on these properties. The dynamic programming framework allows us to show that the optimal value function is piecewise linear and continuous, which enables us to develop polynomial time algorithms for several different problems, including those with backlogging and varying capacities under certain conditions. As special cases, we develop polynomial time algorithms that run in O(n²){\mathcal{O}(n^2)} and O(n²T log n){\mathcal{O}(n^2T\,{\rm log}\,n)} times, respectively for stochastic uncapacitated and constant capacitated lot-sizing problems with backlogging, regardless of the scenario tree structure.     

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

Algorithms for single-machine scheduling with stochastic outtree precedence relations to minimize expected weighted flow time or maximum expected lateness

Stochastic single-machine scheduling problems with special tree-like GERT precedence constraints and expected weighted flow time or maximum expected lateness as objective functions are considered. To obtain polynomial algorithms for these problems, Smith's ratio rule and Lawler's rule for the deterministic problems 1¦outtree¦w _v C _v and 1¦prec¦f _max , respectively, are generalized.     

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

一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究

本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.     

Strong polynomiality of resource constraint propagation

Constraint-based schedulers have been widely successful in tackling complex, disjunctive, and cumulative scheduling applications by combining tree search and constraint propagation. The constraint-propagation step is a fixpoint algorithm that applies pruning operators to tighten the release and due dates of activities using precedence or resource constraints. A variety of pruning operators for resource constraints have been proposed; they are based on edge finding or energetic reasoning and handle a single resource.

Complexity results in this area are only available for a single application of these pruning operators, which is problematic for at least two reasons. On the one hand, the operators are not idempotent, so a single application is rarely sufficient. On the other hand, the operators are not used in isolation but interact with each other. Existing results thus provide a very partial picture of the complexity of propagating resource constraints in constraint-based scheduling.

This paper aims at addressing these limitations. It studies the complexity of applying pruning operators for resource constraints to a fixpoint. In particular, it shows that: (1) the fixpoint of the edge finder for both release and due dates can be reached in strongly polynomial time for disjunctive scheduling; (2) the fixpoint can be reached in strongly polynomial time for updating the release dates or the due dates but not both for the cumulative scheduling; and (3) the fixpoint of “reasonable” energetic operators cannot be reached in strongly polynomial time, even for disjunctive scheduling and even when only the release dates or the due dates are considered.     

Ten notes on equal-processing-time scheduling

Equal-processing-time scheduling problems whose complexity status has been unknown are shown to be solved in polynomial time by well-known and relatively new techniques. Single-machine, parallel-machine, parallel-batch, open-shop, flow-shop and job-shop environments are touched upon.Received: February 2003, Revised: September 2003, AMS classification: 90B35, 68Q25 All correspondence to: Vadim G. Timkovsky     

带广义偏序约束的Flow—shop排序问题

本文研究了一种新的排序问题：带“广义偏序”约束的ｆｏｌｗ－ｓｈｐｏ排序问题。如工件Ｊｊ与工件Ｊｋ之间有广义偏序，则Ｊｊ→Ｊｋ，且Ｊｊ的完工时间与Ｊｋ的开工时间的间隔洋小于ｌｊｋ和不大于ｕｊｋ，０≤ｌｊｋ≤ｕｊｋ。问题的目标函数是最大完工时间。     

Resource leveling in a machine environment

We address resource leveling problems in a machine environment. Given a set of m machines, one or more renewable resources, and a set of n tasks, each assigned to exactly one of the machines. Each task has a processing time, an earliest start time, a deadline, and resource requirements. There are no precedence relations between the tasks. The tasks have to be sequenced on the machines while minimizing a function of the level of resource utilization from each resource over time. We provide various complexity results including a polynomial time algorithm for a one machine special case. We also propose an exact method using various techniques to find optimal or close-to-optimal solutions. The computational experiments show that our exact method significantly outperforms heuristics and a commercial MIP solver.     

On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times

We consider the single machine, serial batching, total completion time scheduling problem with precedence constraints, release dates and identical processing times in this paper. The complexity of this problem is reported as open in the literature. We provide an O(n⁵) time algorithm to solve this problem.     

Single-machine scheduling with precedence constraints and position-dependent processing times

In this paper we consider single-machine scheduling problems with position-dependent processing times, i.e., jobs whose processing times are an increasing or decreasing function of their positions in a processing sequence. In addition, the jobs are related by parallel chains and a series–parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan polynomial algorithms exist.     

Linear preselective policies for stochastic project scheduling

In the context of stochastic resource-constrained project scheduling we introduce a novel class of scheduling policies, the linear preselective policies. They combine the benefits of preselective policies and priority policies; two classes that are well known from both deterministic and stochastic scheduling. We study several properties of this new class of policies which indicate its usefulness for computational purposes. Based on a new representation of preselective policies as and/or precedence constraints we derive efficient algorithms for computing earliest job start times and state a necessary and sufficient dominance criterion for preselective policies.  A computational experiment based on 480 instances empirically validates the theoretical findings.     

Online stochastic optimization under time constraints

This paper considers online stochastic combinatorial optimization problems where uncertainties, i.e., which requests come and when, are characterized by distributions that can be sampled and where time constraints severely limit the number of offline optimizations which can be performed at decision time and/or in between decisions. It proposes online stochastic algorithms that combine the frameworks of online and stochastic optimization. Online stochastic algorithms differ from traditional a priori methods such as stochastic programming and Markov Decision Processes by focusing on the instance data that is revealed over time. The paper proposes three main algorithms: expectation E, consensus C, and regret R. They all make online decisions by approximating, for each decision, the solution to a multi-stage stochastic program using an exterior sampling method and a polynomial number of samples. The algorithms were evaluated experimentally and theoretically. The experimental results were obtained on three applications of different nature: packet scheduling, multiple vehicle routing with time windows, and multiple vehicle dispatching. The theoretical results show that, under assumptions which seem to hold on these, and other, applications, algorithm E has an expected constant loss compared to the offline optimal solution. Algorithm R reduces the number of optimizations by a factor |R|, where R is the number of requests, and has an expected ρ(1+o(1)) loss when the regret gives a ρ-approximation to the offline problem.