TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)Basic Sequencing

COGA 5-Wheel

Page Content

to Navigation

The problems considered here as basic sequencing problems are basically classic machine scheduling problems which reduce to finding a minimum cost sequence of jobs. In the considered setting, the cost incurred by a job solely depends on the neighboring jobs in the sequence or the job's completion time. We investigate the following problems:

This is joint work with Tobias Jacobs (previously in this Priority Programme, later at NII Tokyo). The work on Eulerian extensions is also joint work with Nicole Megow (MPII Saarbrücken).

Generalized Min-Sum-Scheduling

We consider an offline single machine scheduling problem with generalized min-sum objective. In contrast to the classic variant where one aims for minimizing the (weighted) average of completion times or flow times, here some nonlinear cost function is applied to the values beforehand. The choice of  cost function allows to model several objectives. By utilizing Lp-norms (or closely related monomials), one can flexibly compromise between average and worst-case cost. Moreover, the cost function can be interpreted as nonuniform processor speed.

Formally, given a set of n jobs with processing times pj and weight wj for j=1, ..., n, one aims for a sequence of the jobs minimizing ∑j wj g(Cj) where g is some non-decreasing cost function and Cj denotes the completion time of job j.

We show that for piecewise linear  cost functions the problem is strongly NP-hard while it is in P for exponential cost functions. The main theoretical contribution is a tight analysis of the approximation guarantee of Smith's rule (a.k.a. Highest Density First) under any particular convex or concave cost function. In addition, we evaluate the optimality gap of Smith's rule empirically for different monomial cost functions. To overcome unrealistic worst case instances, we also give tight approximation bounds that are parametrized by the minimum, maximum, and total processing time. As the approximation factors tend to be very small, they yield valuable lower bounds on the optimum that can utilized in exact solution methods.

For quadratic cost functions, throughout the past decades, great effort has been made to develop fast exact algorithms. The efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. We enhance the map of known order constraints by proving an extended version of a constraint that has been conjectured by Mondal and Sen (European Journal of Operational Research 125, 2000). Besides proving this conjecture, our main contribution is an extensive experimental study where the influence of different kinds order constraints on the performance of exact algorithms is systematically evaluated. In addition to a best-first graph search algorithm, we test a Quadratic Integer Programming formulation that admits to add order constraints as additional linear constraints.

Our experiments are based on sets of  problem instances that have been generated using  a new method which allows us to adjust a certain degree of difficulty of the instances. They are available for download.

Eulerian Extension Problems

We propose a new technique for considering the complexity of certain sequencing problems like the Gilmore-Gomory type Traveling Salesman Problem (GG-TSP) or the new flowshop problem we investigate in our corresponding publication. These problems have a natural interpretation as Eulerian Extension Problems. Briefly, in this approach for an instance of a sequencing problem, we build a Eulerian graph in which every tour corresponds to an optimal solution and vice versa. The main advantage of this approach is that instead of only one optimal solution, we obtain the entire set of optimal solutions, improving in that sense the original algorithm for the GG-TSP by Gilmore and Gomory (Operations Research, 1964).

The new objective function which we consider for no-wait flowshop scheduling is motivated by the process of strand casting in steel manufacturing. Since idle-times on the last machine, the strand casting machine, cause immense setup times, we aim to minimize the total number of idle times on the last machine in the process.

Production site for steel manufacturing.
Lupe

Using the Eulerian Extension approach, we show that in case of only single-machine stages, this problem is solvable in polynomial time for two processing stages, and it is strongly NP-hard for more processing stages. Furthermore, we show that the problem can still be solved optimally when there are two machine stages and one machine in the first stage. For all other cases we show the strong NP-hardness, thus completely resolving the complexity status of this problem.

Back to main project website.

Publications

An experimental and analytical study of order constraints for single machine scheduling with quadratic cost
Citation key HoehnJacobs2012a
Author Höhn, Wiebke and Jacobs, Tobias
Title of Book Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX)
Pages 103-117
Year 2012
Publisher SIAM
Abstract We consider the problem of scheduling jobs on a single machine. Given a quadratic cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is defined as the cost function value at the job's completion time. Throughout the past decades, great effort has been made to develop fast exact algorithms for the case of quadratic costs. The efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. A considerable number of different kinds of such constraints have been proposed. In this work we enhance the map of known order constraints by proving an extended version of a constraint that has been conjectured by Mondal and Sen more than a decade ago. Besides proving this conjecture, our main contribution is an extensive experimental study where the influence of different kinds order constraints on the performance of exact algorithms is systematically evaluated. In addition to a best-first graph search algorithm, we test a Quadratic Integer Programming formulation that admits to add order constraints as additional linear constraints. We also evaluate the optimality gap of well known Smith's rule for different monomial cost functions. Our experiments are based on sets of problem instances that have been generated using a new method which allows us to adjust a certain degree of difficulty of the instances.
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe