Complex single machine scheduling
| dc.contributor.advisor | Möhring, Rolf H. | en |
| dc.contributor.author | Höhn, Wiebke | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.contributor.referee | Möhring, Rolf H. | en |
| dc.contributor.referee | Lübbecke, Marco E. | en |
| dc.date.accepted | 2013-09-02 | |
| dc.date.accessioned | 2015-11-20T23:12:46Z | |
| dc.date.available | 2014-02-27T12:00:00Z | |
| dc.date.issued | 2014-02-27 | |
| dc.date.submitted | 2014-02-24 | |
| dc.description.abstract | Die Arbeit beschäftigt sich mit komplexen Reihenfolgeproblemen, wie sie ihm Scheduling auftreten, wobei zwei Klassen derartiger Probleme näher beleuchtet werden. Auf der einen Seite betrachten wir ein klassisches Maschinenschedulingproblem, bei dem es darum geht, Jobs auf einer einzelnen Maschine im weitesten Sinne fair zu planen. Der verwendete Fairnessbegriff ist dabei eine Verallgemeinerung der gewichteten Durchschnittsfertigstellungszeit, wobei die Fertigstellungszeiten nicht mehr direkt in die Bewertung einfließen sondern die Fertigstellungskosten, die durch eine nicht-fallende Kostenfunktion auf den Fertigstellungszeiten gegeben werden. Im Gegensatz zu dieser Klasse von Problemen liegt die Schwierigkeit bei der zweiten betrachteten Problemklasse nicht in der komplexen Zielfunktion sondern vielmehr in zahlreichen komplizierten Nebenbedingungen wie sie in der Praxis auftreten. Neben der eigentlichen Produktionsreihenfolge müssen in diesen Problemen weitere Entscheidungen für die gewählte Reihenfolge getroffen werden. Das Ziel ist dabei die Minimierung der Gesamtproduktionsdauer. Für die erste der beiden Problemklassen liegt unser Fokus auf konvexen und konkaven Kostenfunktionen und insbesondere auf Monomen t^k von positiven Grad k. Für diese Klasse von Kostenfunktionen analysieren wir die Approximationsgüte von Smith's Rule, einem Standardalgorithmus im Scheduling. Durch schrittweises Einschränken des Raums möglicher Worst-Case-Instanzen reduzieren wir das Berechnen des scharfen Approximationsfaktors für beliebige feste konvexe oder konkave Kostenfunktion auf ein kontinuierliches Optimierungsproblem mit zwei Freiheitsgraden. Im Fall polynomieller Kostenfunktionen mit positiven Koeffizienten korrespondiert der Approximationsfaktor sogar zur Nullstelle eines Polynoms in nur einer Variablen. Da die Worst-Case-Instanzen sehr viele sehr kleine Jobs und einen sehr großen Job enthalten, bieten wir auch eine realitätsnähere Analyse, die den scharfen Approximationsfaktor in Abhängigkeit der maximalen Produktionsdauer und der Gesamtprododuktionsdauer bei insgesamt ganzzahligen Dauern berechnet. Neben den impliziten Beschreibungen des Approximationsfaktors als Lösung eines kontinuierlichen Optimierungsproblems zeigen wir auch explizite Schranken an den Faktor im Falle von Kostenfunktionen t^k. Insbesondere zeigen wir, dass der asymptotische Approximationsfaktor in diesem Fall k^{(k-1)/(k+1)} ist. Des Weiteren liefern wir für das beschriebene Problem ein erstes starkes NP-Härte-Resultat. Wir zeigen die Härte für stückweise lineare Kostenfunktionen, die jedoch weder konvex noch konkav sind. Bisher war nur bekannt, dass das Problem für allgemeine konvexe Kostenfunktionen schwach NP-schwer ist (Yuan 1992). Neben den Komplexitätsüberlegungen betrachten wir exakte Algorithmen für den Fall quadratischer Kostenfunktionen. Dies beinhaltet insbesondere Reihenfolgeregeln, die bestimmte relative Ordnungen von Jobpaaren in Optimallösungen ausschließen. In diesem Zusammenhang zeigen wir eine entsprechende Reihenfolgeregel, die von Mondal und Sen (2000) vor mehr als 10 Jahren vermutet wurde. Diese und weitere Regeln werden in zugehörigen Experimenten empirisch getestet und evaluiert. Wie bereits erwähnt, widmet sich der zweite Teil der Arbeit komplexen Reihenfolgeproblemen, bei denen selbst festgelegte Produktionsreihenfolgen noch weitere Entscheidungen erfordern. Für diese allgemeine Klasse von Problemen schlagen wir einen generischen Lösungsansatz vor, der den allgemeinen Reihenfolgeaspekt von den sehr problemspezifischen Entscheidungen für eine festgelegte Sequenz trennt. Die Reihenfolgebildung erfolgt mit Hilfe eines genetischen Algorithmus, so dass sich der eigentliche Fokus beim Algorithmendesign darauf verlagert, effiziente Algorithmen für das Teilproblem mit fester Sequenz zu erstellen. Dieser allgemeine Ansatz wurde im Rahmen zweier Praxiskooperationen mit Salzgitter Flachstahl und PSI Metals bzw. Sachsenmilch umgesetzt. Im ersten der beiden Probleme geht es um die Planung einer Bandbeschichtungsanlage mit sogenannten Shuttle-Coatern. Wir zeigen, dass in diesem Fall das Teilproblem, die Entscheidungen für eine feste Sequenz zu treffen, eng verwandt zum Maximum Weight Independent Set Problem in einer Klasse verallgemeinerter Intervallgraphen ist. Ein tiefgründiges Verständnis dieses Problems, u.A. Einsichten in die Komplexität einschließend, hat am Ende die Basis dafür gelegt, dass mit unserem Algorithmus im Schnitt mehr als 13% der Gesamtproduktionszeit an der Coil-Coating-Anlage unseres Kooperationspartners Salzgitter Flachstahl eingespart werden konnte. Bei dem zweiten Problem handelt es sich um die Planung einer Abfüllanlage in der Molkereiproduktion. Dort hat der Algorithmus, der für dieses Problem entwickelt wurde, Lösungen erzeugt, die mit der Qualität der manuell geplanten Lösungen von Sachsenmilch übereinstimmen, wobei wir zeigen konnten, dass die Optimalitätslücke nicht größer als 2% ist. | de |
| dc.description.abstract | This thesis deals with complex sequencing problems as they appear in many scheduling applications. The focus is on two classes of such kind of problems. Firstly, we address a classic machine scheduling problem which aims at computing schedules for a single machine which are in the broadest sense fair. The considered definition of fairness generalizes the weighted average completion time in terms of not considering the completion times of the jobs directly but their more general cost which is given by some non-decreasing cost function on the completion times. In contrast to this class of problems, the challenges of the second problem class are not complex objective functions but rather countless complicated side constraints that stem from applications in practice. In addition to the actual processing sequence in these problems further decisions have to be taken for the chosen sequence, aiming for the overall goal of minimizing the makespan. The focus in the first problem is on convex and concave cost functions and in particular on monomials t^k with positive degree k. For this class of cost functions, we analyze the approximation guarantee of Smith's rule, a classic algorithm in machine scheduling. By largely restricting the set of potential worst-case instances, we reduce the computation of the tight approximation factor of Smith's rule for any given fixed convex or concave cost function to a standard continuous optimization problem on two variables. For polynomial functions with non-negative coefficients, the tight approximation factor even corresponds to the root of a univariate polynomial. Since the worst-case instances contain very many very small jobs and one very large job, we also provide a more realistic analysis which is again tight, and which is parametrized by the total processing time and the maximum processing time, given that all processing times are integral. In addition to the above implicit description of the approximation factor as a solution of a continuous optimization problem, for the case of monomial cost functions t^k, we also give explicit lower and upper bounds on this tight factor. In particular, we show that the asymptotic approximation factor is k^{(k-1)/(k+1)} in this case. Moreover, we give a first strong NP-hardness result for the described scheduling problem. While so far only the weak NP-hardness in the case of general convex cost functions was known (Yuan 1992), we now show that the problem is strongly NP-hard for piece-wise linear functions, however, which are neither convex nor concave. Besides these complexity considerations, we also address exact algorithms for the special case of quadratic cost. This involves in particular certain order rules which rule out relative orders of job pairs in optimal solutions. In this context, we prove such an order rule that was conjectured by Mondal and Sen (2000) more than 10 years ago. This and further order rules are evaluated empirically. As mentioned above, the second class of problems addresses sequencing problems in which even a fixed processing sequence still requires further non-trivial decisions. For this very general class of problems, we propose a generic algorithmic approach which separates the general sequencing aspect from the very problem-specific decisions that have to be taken for a chosen sequence. The sequencing is based on a genetic algorithm so that the main focus shifts to designing efficient algorithms for the fixed-sequence subproblem. In cooperations with Salzgitter Flachstahl and PSI Metals as well as with Sachsenmilch, this approach is applied to problems from steel industry and dairy industry, respectively. The first of these two problems deals with the planning of a coil coating line with so called shuttle coaters. We show that in this case, the fixed-sequence subproblem is strongly related to the Maximum Weight Independent Set Problem in a class of generalized interval graphs. In the end, a thorough understanding of this subproblem, among others including insights into the complexity of the problem, were the key for the overall algorithm to reduce the makespan by over 13% on average at the coil coating line of our partner Salzgitter Flachstahl. The second problem considers the planning of a filling line in dairy industry. Our algorithm designed for this problem produced solutions which are en par with the solutions we got from our partner Sachsenmilch. However, we could show that the optimality gap of those solutions is not larger than 2%. | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus4-47972 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/4266 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-3969 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 500 Naturwissenschaften und Mathematik | en |
| dc.subject.other | Approximationsalgorithmen | de |
| dc.subject.other | Kombinatorische Optimierung | de |
| dc.subject.other | Reihenfolgeplanung | de |
| dc.subject.other | Scheduling | de |
| dc.subject.other | Stahlproduktion | de |
| dc.subject.other | Approximation algorithms | en |
| dc.subject.other | Combinatorial optimization | en |
| dc.subject.other | Scheduling | en |
| dc.subject.other | Sequencing problems | en |
| dc.subject.other | Steel production | en |
| dc.title | Complex single machine scheduling | en |
| dc.title.subtitle | Theoretical and practical aspects of sequencing | en |
| dc.title.translated | Komplexes Single-Machine-Scheduling | de |
| dc.title.translatedsubtitle | theoretische und praktische Aspekte in der Reihenfolgeplanung | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus4 | 4797 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1