Walter, Rico ; Wirth, Martin ; Lawrinenko, Alexander (2017)
Improved approaches to the exact solution of the machine covering problem.
In: Journal of Scheduling, 20
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
For the basic problem of scheduling a set of n independent jobs on a set of m identical parallel machines with the objective of maximizing the minimum machine completion time---also referred to as machine covering---we propose a new exact branch-and-bound algorithm. Its most distinctive components are a different symmetry-breaking solution representation, enhanced lower and upper bounds, and effective novel dominance criteria derived from structural patterns of optimal schedules. Results of a comprehensive computational study conducted on benchmark instances attest to the effectiveness of our approach, particularly for small ratios of n to m.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2017 |
| Autor(en): | Walter, Rico ; Wirth, Martin ; Lawrinenko, Alexander |
| Art des Eintrags: | Bibliographie |
| Titel: | Improved approaches to the exact solution of the machine covering problem |
| Sprache: | Deutsch |
| Publikationsjahr: | 2017 |
| Verlag: | Springer |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Journal of Scheduling |
| Jahrgang/Volume einer Zeitschrift: | 20 |
| URL / URN: | http://dx.doi.org/10.1007/s10951-016-0477-x |
| Kurzbeschreibung (Abstract): | For the basic problem of scheduling a set of n independent jobs on a set of m identical parallel machines with the objective of maximizing the minimum machine completion time---also referred to as machine covering---we propose a new exact branch-and-bound algorithm. Its most distinctive components are a different symmetry-breaking solution representation, enhanced lower and upper bounds, and effective novel dominance criteria derived from structural patterns of optimal schedules. Results of a comprehensive computational study conducted on benchmark instances attest to the effectiveness of our approach, particularly for small ratios of n to m. |
| Fachbereich(e)/-gebiet(e): | 01 Fachbereich Rechts- und Wirtschaftswissenschaften > Betriebswirtschaftliche Fachgebiete > Fachgebiet Management Science / Operations Research 01 Fachbereich Rechts- und Wirtschaftswissenschaften 01 Fachbereich Rechts- und Wirtschaftswissenschaften > Betriebswirtschaftliche Fachgebiete |
| Hinterlegungsdatum: | 28 Apr 2016 12:41 |
| Letzte Änderung: | 15 Jun 2020 08:13 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum