TU Darmstadt / ULB / TUbiblio

Improved approaches to the exact solution of the machine covering problem

Walter, Rico and Wirth, Martin and Lawrinenko, Alexander (2016):
Improved approaches to the exact solution of the machine covering problem.
In: Journal of Scheduling, Springer, pp. 1-18, ISSN 1099-1425, [Online-Edition: http://dx.doi.org/10.1007/s10951-016-0477-x],
[Article]

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.

Item Type: Article
Erschienen: 2016
Creators: Walter, Rico and Wirth, Martin and Lawrinenko, Alexander
Title: Improved approaches to the exact solution of the machine covering problem
Language: German
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.

Journal or Publication Title: Journal of Scheduling
Publisher: Springer
Divisions: 01 Department of Law and Economics > Betriebswirtschaftliche Fachgebiete > Fachgebiet Management Science / Operations Research
01 Department of Law and Economics > Betriebswirtschaftliche Fachgebiete
01 Department of Law and Economics
Date Deposited: 28 Apr 2016 12:41
Official URL: http://dx.doi.org/10.1007/s10951-016-0477-x
Export:

Optionen (nur für Redakteure)

View Item View Item