TU Berlin

Wiebke HöhnPublikationen

Inhalt des Dokuments

zur Navigation

Publikationen

Publikationen in Konferenzbänden

Höhn, W., Mestre, J. and Wiese, A.
How Unsplittable-Flow-Covering helps Scheduling with Job-Dependent Cost Functions.
In Proc. of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), LNCS, Vol. 8572, pp. 625-636, Springer, 2014.  [pdf]


Höhn, W. and Jacobs, T.
An experimental and analytical study of order constraints for single machine scheduling with quadratic cost.
In Proc. of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 103-117, SIAM, 2012.  [pdf]


Höhn, W. and Jacobs, T.
On the performance of Smith's rule in single-machine scheduling with nonlinear cost.
In Proc. of the 10th Latin American Theoretical Informatics Symposium (LATIN), LNCS, Vol. 7256, pp. 482-493, Springer, 2012.  [pdf]


Publikationen in Journalen

On Eulerian extensions and their application to no-wait flowshop scheduling
Zitatschlüssel HoehnJacobsMegow2012
Autor Höhn, Wiebke and Jacobs, Tobias and Megow, Nicole
Seiten 295-309
Jahr 2012
DOI 10.1007/s10951-011-0241-1
Journal Journal of Scheduling
Jahrgang 15
Nummer 3
Verlag Springer
Zusammenfassung 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.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Hinweis zum Copyright

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe