Tazari, Siamak ; Müller-Hannemann, Matthias ; Weihe, Karsten (2006)
Workload Balancing in Multi-Stage Production Processes.
5th International Workshop (WEA 2006). Cala Galdana, Menorca, Spain (24.05.2006-27.05.2006)
doi: 10.1007/11764298_5
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (Abstract)
We consider a variant on the general workload balancing problem, which arises naturally in automated manufacturing and throughput optimization of assembly-lines. The problem is to distribute the tasks over compatible machines and phases of the process simultaneously. The total duration of all phases is to be minimized. We have proved that this variant is NP-hard (even for uniform task lengths), and we propose a novel algorithmic approach. Our approach includes an exact solver for the case of uniform task lengths, which is based on network-flow techniques and runs in polynomial time for a fixed number of phases (the number of phases is indeed very small in practice). To solve the general case with arbitrary real task lengths, we combine our solver for uniform task lengths with a shortest-path based multi-exchange local search.
We present results of an extensive computational study on real-world examples from printed circuit board manufacturing. This study demonstrates that our approach is very promising. The solution quality obtained by our approach is compared with lower bounds from an integer linear programming model. It turns out that our approach is faster than CPLEX by orders of magnitude, and the optimality gap is quite small.
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2006 |
| Autor(en): | Tazari, Siamak ; Müller-Hannemann, Matthias ; Weihe, Karsten |
| Art des Eintrags: | Bibliographie |
| Titel: | Workload Balancing in Multi-Stage Production Processes |
| Sprache: | Deutsch |
| Publikationsjahr: | 2006 |
| Ort: | Berlin |
| Verlag: | Springer |
| Buchtitel: | Experimental Algorithms: 5th International Workshop, WEA 2006, Cala Galdana, Menorca, Spain, May 24-27, 2006, Proceedings |
| Reihe: | Lecture notes in computer science |
| Band einer Reihe: | 4007 |
| Veranstaltungstitel: | 5th International Workshop (WEA 2006) |
| Veranstaltungsort: | Cala Galdana, Menorca, Spain |
| Veranstaltungsdatum: | 24.05.2006-27.05.2006 |
| DOI: | 10.1007/11764298_5 |
| Kurzbeschreibung (Abstract): | We consider a variant on the general workload balancing problem, which arises naturally in automated manufacturing and throughput optimization of assembly-lines. The problem is to distribute the tasks over compatible machines and phases of the process simultaneously. The total duration of all phases is to be minimized. We have proved that this variant is NP-hard (even for uniform task lengths), and we propose a novel algorithmic approach. Our approach includes an exact solver for the case of uniform task lengths, which is based on network-flow techniques and runs in polynomial time for a fixed number of phases (the number of phases is indeed very small in practice). To solve the general case with arbitrary real task lengths, we combine our solver for uniform task lengths with a shortest-path based multi-exchange local search. We present results of an extensive computational study on real-world examples from printed circuit board manufacturing. This study demonstrates that our approach is very promising. The solution quality obtained by our approach is compared with lower bounds from an integer linear programming model. It turns out that our approach is faster than CPLEX by orders of magnitude, and the optimality gap is quite small. |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Algorithmik |
| Hinterlegungsdatum: | 20 Nov 2008 08:25 |
| Letzte Änderung: | 29 Nov 2024 09:48 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum