### Page Content

# Basic Sequencing

- [1]
- © DFG

Part of the project "Algorithms for Complex Scheduling Problems" [2]

within DFG Priority Programme 1307 "Algorithm Engineering" [3]

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:

- generalized min-sum scheduling
- Eulerian extension problems

This is joint work with Tobias Jacobs (previously in this Priority Programme [4], 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 L_{p}-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
*p _{j}* and weight

*w*for

_{j}*j=1, ..., n,*one aims for a sequence of the jobs minimizing ∑

_{j}

*w*where

_{j}g(C_{j})*g*is some non-decreasing cost function and

*C*denotes the completion time of job

_{j}*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 [5].

## 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.
- [6]
- © COGA

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. [7]

## Publications

Citation key | HoehnJacobsMegow2012 |
---|---|

Author | Höhn, Wiebke and Jacobs, Tobias and Megow, Nicole |

Pages | 295-309 |

Year | 2012 |

DOI | 10.1007/s10951-011-0241-1 |

Journal | Journal of Scheduling |

Volume | 15 |

Number | 3 |

Publisher | Springer |

Abstract | We consider a variant of no-wait flowshop scheduling that is motivated by continuous casting in the multistage production process in steel manufacturing. The task is to find a feasible schedule with a minimum number of interruptions, i.e., continuous idle time intervals on the last production stage. Based on an interpretation as Eulerian Extension Problems, we fully settle the complexity status of any particular problem case: We give a very intuitive optimal algorithm for scheduling on two processing stages with one machine in the first stage, and we show that all other problem variants are strongly NP-hard. We also discuss alternative idle time related scheduling models and their justification in the considered steel manufacturing environment. Here, we derive constant factor approximations. |

Back [11]

ebseite/AG_DiskAlg/FG_KombOptGraphAlg/logos/dfg-algorit

hm-engineering-medium.jpg

lex_scheduling/parameter/en/minhilfe/

464-5/

lex_scheduling/generalized_min_sum_scheduling_instance_

library/parameter/en/minhilfe/

ebseite/AG_DiskAlg/FG_KombOptGraphAlg/projects/SPP-Comp

lex-Scheduling/strand-casting.gif

lex_scheduling/parameter/en/minhilfe/

d/AG_DiskAlg/FG_KombOptGraphAlg/paper/2012/HoehnJacobsM

egow2012.pdf

4/

plex_scheduling/basic_sequencing/parameter/en/minhilfe/

?no_cache=1&tx_sibibtex_pi1%5Bdownload_bibtex_uid%5

D=238208&tx_sibibtex_pi1%5Bcontentelement%5D=tt_con

tent%3A405448

plex_scheduling/basic_sequencing/parameter/en/minhilfe/