Disruption management for resource-constrained project scheduling

In this paper, we study the problem of how to react when an ongoing project is disrupted. The focus is on the resource-constrained project scheduling problem with finish–start precedence constraints. We begin by proposing a classification scheme for the different types of disruptions and then define the constraints and objectives that comprise what we call the recovery problem. The goal is to get back on track as soon as possible at minimum cost, where cost is now a function of the deviation from the original schedule. The problem is formulated as an integer linear program and solved with a hybrid mixed-inter programming/constraint programming procedure that exploits a number of special features in the constraints. The new model is significantly different from the original one due to the fact that a different set of feasibility conditions and performance requirements must be considered during the recovery process. The complexity of several special cases is analysed. To test the hybrid procedure, 554 20-activity instances were solved and the results compared with those obtained with CPLEX. Computational experiments were also conducted to determine the effects of different factors related to the recovery process.     

Discrete time/cost trade-offs in project scheduling with time-switch constraints

The discrete time/cost trade-off problem assumes the duration of project activities to be discrete, non-increasing functions of the amount of a single non-renewable resource. The problem has been studied under three possible objectives. The so-called deadline problem involves the scheduling of project activities in order to minimize the total cost of the project while meeting a given deadline. The budget problem aims at minimizing the project duration without exceeding a given budget. A third objective involves the generation of the complete efficient time/cost profile over the set of feasible project durations. In this paper we describe a solution procedure for the deadline problem in which three special cases of time-switch constraints are involved. These constraints impose a specified starting time on the project activities and force them to be inactive during specified time periods. We propose a branch-and-bound algorithm and a heuristic procedure which both make use of a lower bound calculation for the discrete time/cost trade-off problem (without time-switch constraints). The procedures have been coded in Visual C++, version 6.0 under Windows 2000 and have been validated on a randomly generated problem set. We also discuss an illustrative example based on a real-life situation.     

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.     

On the Complexity of Equalizing Inequalities

We study two approaches to replace a finite mathematical programming problem with inequality constraints by a problem that contains only equality constraints. The first approach lifts the feasible set into a high-dimensional space by the introduction of quadratic slack variables. We show that then not only the number of critical points but also the topological complexity of the feasible set grow exponentially. On the other hand, the second approach bases on an interior point technique and lifts an approximation of the feasible set into a space with only one additional dimension. Here only Karush–Kuhn–Tucker points with respect to the positive and negative objective function in the original problem give rise to critical points of the smoothed problem, so that the number of critical points as well as the topological complexity can at most double.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25     

A new heuristic for the multi-mode resource investment problem

This paper considers the problem of minimizing resource investment required to execute the tasks in a project network by a given project due date. A project consists of non-pre-emptive tasks executed in a known and required precedence order. Each task is completed in one of its feasible modes, which may differ not only in task duration but also in consumption of renewable resources. A priority rule heuristic with polynomial computational complexity is presented for this computationally intractable problem. This heuristic simultaneously considers due date constraints and resource usage to select and schedule tasks with one decision rule. This differs from prior multi-mode priority rule scheduling heuristics that apply two consecutive decision rules to schedule tasks. Extensive computational testing indicates promising results.     

Complexity and algorithms for nonlinear optimization problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005.     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.     

Infinite-dimensional quadratic optimization: Interior-point methods and control applications

An infinite-dimensional convex optimization problem with the linear-quadratic cost function and linear-quadratic constraints is considered. We generalize the interior-point techniques of Nesterov-Nemirovsky to this infinite-dimensional situation. The complexity estimates obtained are similar to finite-dimensional ones. We apply our results to the linear-quadratic control problem with quadratic constraints. It is shown that for this problem the Newton step is basically reduced to the standard LQ problem. This research was supported in part by the Cooperative Research Centre for Robust and Adaptive Systems while the first author visited the Australian National University and by NSF Grant DMS 94-23279.     

Optimal workforce assignment to operations of a paced assembly line

We study a paced assembly line intended for manufacturing different products. Workers with identical skills perform non-preemptable operations whose assignment to stations is known. Operations assigned to the same station are executed sequentially, and they should follow the given precedence relations. Operations assigned to different stations can be performed in parallel. The operation’s processing time depends on the number of workers performing this operation. The problem consists in assigning workers to operations such that the maximal number of workers employed simultaneously in the assembly line is minimized, the line cycle time is not exceeded and the box constraints specifying the possible number of workers for each operation are not violated. We show that the general problem is NP-hard in the strong sense, develop conventional and randomized heuristics, propose a reduction to a series of feasibility problems, present a MILP model for the feasibility problem, show relation of the feasibility problem to multi-mode project scheduling and multiprocessor scheduling, establish computational complexity of several special cases based on this relation and provide computer experiments with real and simulated data.     

An Analysis of Partially Clairvoyant Scheduling

Real-time scheduling problems confront two issues not addressed by traditional scheduling models, viz., parameter variability and the existence of complex relationships constraining the executions of jobs. Accordingly, modeling becomes crucial in the specification of scheduling problems in such systems. In this paper, we analyze scheduling algorithms in Partially Clairvoyant Real-time scheduling systems and present a new dual-based algorithm for the feasibility problem in the case of strict relative constraints. We also study the problem of online dispatching in Partially Clairvoyant systems and show that the complexity of dispatching is logarithmically related to the complexity of the schedulability problem.     

Scheduling three chains on two parallel machines

We consider the problem of scheduling n tasks subject to chain-precedence constraints on two identical machines with the objective of minimizing the makespan. The problem is known to be strongly NP-hard. Here, we prove that it is binary NP-hard even with three chains. Furthermore, we characterize the complexity of this case by presenting a pseudopolynomial time algorithm and a fully polynomial time approximation scheme.     

An Exact Procedure for the Resource-Constrained Weighted Earliness–Tardiness Project Scheduling Problem

In this paper we study the resource-constrained project scheduling problem with weighted earliness–tardinesss penalty costs. Project activities are assumed to have a known deterministic due date, a unit earliness as well as a unit tardiness penalty cost and constant renewable resource requirements. The objective is to schedule the activities in order to minimize the total weighted earliness–tardinesss penalty cost of the project subject to the finish–start precedence constraints and the constant renewable resource availability constraints. With these features the problem becomes highly attractive in just-in-time environments.We introduce a depth-first branch-and-bound algorithm which makes use of extra precedence relations to resolve resource conflicts and relies on a fast recursive search algorithm for the unconstrained weighted earliness–tardinesss problem to compute lower bounds. The procedure has been coded in Visual C++, version 4.0 under Windows NT. Both the recursive search algorithm and the branch-and-bound procedure have been validated on a randomly generated problem set.     

A multiobjective evolutionary approach for linearly constrained project selection under uncertainty

In the project selection problem a decision maker is required to allocate limited resources among an available set of competing projects. These projects could arise, although not exclusively, in an R&D, information technology or capital budgeting context. We propose an evolutionary method for project selection problems with partially funded projects, multiple (stochastic) objectives, project interdependencies (in the objectives), and a linear structure for resource constraints. The method is based on posterior articulation of preferences and is able to approximate the efficient frontier composed of stochastically nondominated solutions. We compared the method with the stochastic parameter space investigation method (PSI) and illustrate it by means of an R&D portfolio problem under uncertainty based on Monte Carlo simulation.     

Scheduling: Agreement graph vs resource constraints

We investigate two scheduling problems. The first is scheduling with agreements (SWA) that consists in scheduling a set of jobs non-preemptively on identical machines in a minimum time, subject to constraints that only some specific jobs can be scheduled concurrently. These constraints are represented by an agreement graph. We extend the NP-hardness of SWA with three distinct values of processing times to only two values and this definitely closes the complexity status of SWA on two machines with two fixed processing times. The second problem is the so-called resource-constrained scheduling. We prove that SWA is polynomially equivalent to a special case of the resource-constrained scheduling and deduce new complexity results of the latter.     

Heuristics for multimode scheduling problems with dedicated resources

We study scheduling problems with multiple modes and dedicated resources arising in production and project management, which constitute a special class of the general multimode resource-constrained project scheduling problem. A task may require simultaneously a set of discrete, renewable resources to be processed and the processing can be performed in different modes, that is with different resource sets, processing times, or costs. Precedence constraints can exist among tasks. The total budget that can be allocated to the project can be limited. The problem consists of identifying a mode for each task and a starting time for its processing respecting precedence, resource, and budget constraints. A graph model and an iterative solution scheme are presented. Specific heuristic algorithms for the cases with and without budget constraints are given and computational results are discussed.     

Fixed-parameter algorithms for protein similarity search under mRNA structure constraints

In the context of protein engineering, we consider the problem of computing an mRNA sequence of maximal codon-wise similarity to a given mRNA (and consequently, to a given protein) that additionally satisfies some secondary structure constraints, the so-called mRNA Structure Optimization (MRSO) problem. Since MRSO is known to be APX-hard, Bongartz [D. Bongartz, Some notes on the complexity of protein similarity search under mRNA structure constraints, in: Proc. of the 30th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2004, pp. 174–183] suggested to attack the problem using the approach of parameterized complexity. In this paper we propose three fixed-parameter algorithms that apply for several interesting parameters of MRSO. We believe these algorithms to be relevant for practical applications today, as well as for possible future applications. Furthermore, our results extend the known tractability borderline of MRSO, and provide new research horizons for further improvements of this sort.     

Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem

We study the computational complexity of the Spare Capacity Allocation problem arising in optical networks that use a shared mesh restoration scheme. In this problem we are given a network with edge capacities and point-to-point demands, and the goal is to allocate two edge-disjoint paths for each demand (a working path and a so-called restoration path, which is activated only if the working path fails) so that the capacity constraints are satisfied and the total cost of the used and reserved bandwidth is minimized. We focus on the setting where we deal with a group of demands together, and select their restoration paths simultaneously in order to minimize the total cost. We investigate how the computational complexity of this problem is affected by certain parameters, such as the number of restoration paths to be selected, or the treewidth of the network graph. To analyze the complexity of the problem, we introduce a generalization of the Steiner Forest problem that we call Multicost Steiner Subgraph. We study its parameterized complexity, and identify computationally easy and hard cases by providing hardness proofs as well as efficient (fixed-parameter tractable) algorithms.     

Equality Constraints in Multiobjective Robust Design Optimization: Decision Making Problem

Robust design optimization (RDO) problems can generally be formulated by incorporating uncertainty into the corresponding deterministic problems. In this context, a careful formulation of deterministic equality constraints into the robust domain is necessary to avoid infeasible designs under uncertain conditions. The challenge of formulating equality constraints is compounded in multiobjective RDO problems. Modeling the tradeoffs between the mean of the performance and the variation of the performance for each design objective in a multiobjective RDO problem is itself a complex task. A judicious formulation of equality constraints adds to this complexity because additional tradeoffs are introduced between constraint satisfaction under uncertainty and multiobjective performance. Equality constraints under uncertainty in multiobjective problems can therefore pose a complicated decision making problem. In this paper, we provide a new problem formulation that can be used as an effective multiobjective decision making tool, with emphasis on equality constraints. We present two numerical examples to illustrate our theoretical developments.