On Dual Based Lower Bounds for the Sequential Ordering Problem with Precedences and Due Dates

The Sequential Ordering Problem (herewith, SOP) with precedence relationships was introduced in Escudero (1988), and extended to cover release and due dates in Escudero and Sciomachen (1993). It has a broad range of applications, mainly in production planning for manufacturing systems. The problem consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the nodes and the arcs, satisfying precedence relationships among the nodes and given lower and upper bounds on the weights of the Hamiltonian subpaths. In this paper we present a model for the constrained minimum weight Hamiltonian path problem with precedences and due dates forcing constraints, and introduce related valid cuts that can be used in a separation framework for the dual (Lagrangian based) relaxation of the problem. We also provide an heuristic separation procedure to obtain those cuts, so-called the Lagrangian Relax-and-Cut (LRC) scheme. Computational experience is given for variations of some SOP cases already reported in the literature.     

On due-date based valid cuts for the sequential ordering problem

The Sequential Ordering Problem with precedence relationships was introduced in Escudero (1988), and extended to cover release and due dates in Escudero and Schiomachen (1993). The problem consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the nodes and the arcs, satisfying precedence relationships among the nodes and lower and upper bounds on the Hamiltonian subpaths. In this paper we introduce valid cuts derived from the due date constraints that can be used in a separation framework for the dual (Lagrangian based) relaxation of the problem. We also provide an heuristic separation algorithm to obtain those cuts. This research was supported by DGICYT through grant N. PB95-0407     

Local search procedures for improving feasible solutions to the sequential ordering problem

Given a digraphG=(V, A), a weight for each node inV and a weight for each arc inA, the Sequential Ordering Problem (SOP) consists of finding a Hamiltonian path, such that a release date and a deadline for each node and precedence relationships among nodes are satisfied and a linear function is minimized. In our case, the objective function is the maximum cumulated potential of the nodes (also, the so-called makespan). The SOP has a broad range of applications, mainly in production planning and manufacturing systems. Nodes represent jobs (to be processed on a single machine), arcs represent sequencing of the jobs, the nodes' weights are the processing time for the jobs, the arcs' weights are the setup times for two consecutive jobs, and the cumulated potential of a node is the completion time of a job. The goal is to produce a feasible scheduling of the jobs so that the makespan is minimized. We present an approximate algorithm for improving feasible solutions to the SOP. The algorithm is based on two local search-opt procedures to reduce the makespan while satisfying the time window (i.e. release date and deadline) and precedence constraints, for=3 and 4. The complexity of the algorithm isO(bn ⁴), wheren denotes the number of nodes andb is the average number of precedences per node. Extensive computational experience and implementation aspects are reported for very large-scale instances up to 3000 nodes and 9000 precedences. Experience with real-life cases is also reported.     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为$2-\frac 2m$,其中$m$是机器数目。     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题，目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时，两类问题在一般优先图上都是强NP-困难的，而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界，并基于许可工件之间的最大匹配设计近似算法，其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题，我们在理论上证明了算法的近似比为$2-\frac 2m$，其中$m$是机器数目。     

Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems

Given the minimum Hamiltonian path (or traveling salesman tour) H⁰ in an undirected weighted graph, the sensitivity analysis problem consists in finding by how much we can perturb each edge weight individually without changing the optimality of H⁰.

The maximum increment and decrement of the edge weight that preserve the optimality of H⁰ is called edge tolerance with respect to the solution H⁰. A method of computing lower bounds of edge tolerances based on solving the sensitivity analysis problem for appropriate relaxations of the minimum Hamiltonian path and traveling salesman problems is presented.     

Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound

A stochastic branch-and-bound technique for the solution of stochastic single-machine-tardiness problems with job weights is presented. The technique relies on partitioning the solution space and estimating lower and upper bounds by sampling. For the lower bound estimation, two different types of sampling (“within” and “without” the minimization) are combined. Convergence to the optimal solution (with probability one) can be demonstrated. The approach is generalizable to other discrete stochastic optimization problems. In computational experiments with the single-machine-tardiness problem, the technique worked well for problem instances with a relatively small number of jobs; due to the enormous complexity of the problem, only approximate solutions can be expected for a larger number of jobs. Furthermore, a general precedence rule for the single-machine scheduling of jobs with uncertain processing times has been derived, essentially saying that “safe” jobs are to be scheduled before “unsafe” jobs.     

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.     

Multi-machine scheduling lower bounds using decision diagrams

We consider parallel multi-machine scheduling with due times, where a partition of jobs is given where jobs in the same partition have a common release time, possibly precedence constraints, and cannot overlap. A formulation of decision diagrams for this problem greatly improves upon a more natural extension of the state-of-the-art for single-machine scheduling, and can provide decent lower bounds, outperforming existing solvers given the same short runtime limit, for problem instances with large time scales and tight due times.     

Solving a class of two-resource allocation problem by equivalent load method

We present an efficient algorithm for solving a class of two-resource allocation problem defined on a series-parallel graph, where nodes represent tasks of a given project and arcs represent precedence relationships. Two separate workloads are associated with each task and the time to complete a workload is inversely proportional to the amount of resource allocated. The time to complete a task is the maximum of the times taken to complete the two workloads. The problem is to allocate the two resources across the project so as to minimize the project duration. The proposed algorithm is derived based on the Equivalent Load Method by Monma, Schrijver, Todd, and Wei for the single-resource allocation problem.     

Lower Bounds for Scheduling a Single Robot in a Job-Shop Environment

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the traveling salesman problem with time windows, where additionally generalized precedence constraints (minimal time-lags) have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all traveling and waiting times is minimized.We calculate lower bounds for this problem using constraint propagation techniques and a linear programming formulation which is solved by a column generation procedure. Computational results are presented for test data arising from job-shop instances with a single transport robot and some modified traveling salesman instances.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

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.     

Long-term staffing based on qualification profiles

Manpower still is one of the most expensive resources, in spite of increasing automation. While employee scheduling and rostering has been the topic of extensive research over the past decades, usually it is assumed that the demand for staff is either given or can be obtained without difficulty. In this research we provide an integer programming model for long-term staffing decisions which fits to the needs of manufacturing-to-order companies. The model is based on qualification profiles, the number of which grows exponentially in terms of the number of processes considered. In order to compute tight lower bounds we provide a column generation technique. The subproblem is a shortest path problem in a network where the arcs have multiple weights. Upper bounds, that is, feasible solutions are calculated by means of local search. We present computational results for randomly generated instances and empirical results for examples from practice. The results show that substantial cost savings can be achieved.     

An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations

In this paper we propose an exact algorithm for the Resource Constrained Project Scheduling Problem (RCPSP) with generalized precedence relationships (GPRs) and minimum makespan objective. For the RCPSP with GPRs we give a new mathematical formulation and a branch and bound algorithm exploiting such a formulation. The exact algorithm takes advantage also of a lower bound based on a Lagrangian relaxation of the same mathematical formulation. We provide an extensive experimentation and a comparison with known lower bounds and competing exact algorithms drawn from the state of the art.     

An exact algorithm for the precedence-constrained single-machine scheduling problem

This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors’ previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness–tardiness problems, and most instances with 100 jobs of the former problem.     

Multi-criteria approximation schemes for the resource constrained shortest path problem

In the resource constrained shortest path problem we are given a directed graph along with a source node and a destination node, and each arc has a cost and a vector of weights specifying its requirements from a set of resources with finite budget limits. A minimum cost source-destination path is sought such that the total consumption of the arcs from each resource does not exceed its budget limit. In the case of constant number of weight functions we give a fully polynomial time multi-criteria approximation scheme for the problem which returns a source-destination path of cost at most the optimum, however, the path may slightly violate the budget limits. On the negative side, we show that there does not exist a polynomial time multi-criteria approximation scheme for the problem if the number of weight functions is not a constant. The latter result applies to a broad class of problems as well, including the multi-dimensional knapsack, the multi-budgeted spanning tree, the multi-budgeted matroid basis and the multi-budgeted bipartite perfect matching problems.     

Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound

In this paper we study the Resource Constrained Project Scheduling Problem (RCPSP) with “Feeding Precedence” (FP) constraints and minimum makespan objective. This problem typically arises in production planning environment, like make-to-order manufacturing, where the effort associated with the execution of an activity is not univocally related to its duration percentage and the traditional finish-to-start precedence constraints or the generalized precedence relations cannot completely represent the overlapping among activities. In this context, we need to introduce in the RCPSP the FP constraints. For this problem we propose a new mathematical formulation and define a lower bound based on the Lagrangian relaxation of the resource constraints. A computational experimentation on randomly generated instances of sizes of up to 100 activities shows a better performance of this lower bound when compared to other lower bounds. Moreover, for the optimally solved instances, its value is very close to the optimal one. Furthermore, in order to show the effectiveness of the proposed lower bound on large instances for which the optimal solution is known, we adapted our approach to solve the benchmarks of the basic RCPSP from the PSLIB with 120 activities.     

Data dependent worst case bounds for weighted set packing

We develop data dependent worst case bounds for three simple greedy algorithms for the maximum weighted independent set problem applied to maximum weighted set packing. We exploit the property that the generated output will attain at least a certain weight. These weight quantities are a function of the individual weights corresponding to the vertices of the problem. By using an argument based on linear programming duality we develop a priori bounds that are a function of the minimum guaranteed weight quantities, the highest average reward for a ground item, and cardinality of the ground set. This extends the current bounds which are only a function of the maximum vertex degree in the associated conflict graph. Examples are given that show the benefits of incorporating this data dependent information into bounds.     

Minimizing mean tardiness subject to unspecified minimum number tardy for a single machine

In this paper we propose a hybrid branch and bound algorithm for solving the problem of minimizing mean tardiness for a single machine problem subject to minimum number of tardy jobs. Although the minimum number of tardy jobs is known, the subset of tardy job is not known. The proposed algorithm uses traditional branch and bound scheme where lower bounds on mean tardiness are calculated coupled with using the information that the number of tardy jobs is known. It also uses an insertion algorithm which determines the optimal mean tardiness once the subset of tardy jobs is specified. An example is solved to illustrate the developed procedure.