Improved approaches to the exact solution of the machine covering problem

Rico Walter, Martin Wirth and Alexander Lawrinenko

Publications of Darmstadt Technical University, Institute for Business Studies (BWL) from Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL)

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.

Date: 2017
New Economics Papers: this item is included in nep-cmp and nep-pke
Note: for complete metadata visit http://tubiblio.ulb.tu-darmstadt.de/80530/
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Published in Journal of Scheduling (2017) : pp. 147-164

Downloads: (external link)
http://dx.doi.org/10.1007/s10951-016-0477-x

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:dar:wpaper:80530

Access Statistics for this paper

More papers in Publications of Darmstadt Technical University, Institute for Business Studies (BWL) from Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL) Contact information at EDIRC.
Bibliographic data for series maintained by Dekanatssekretariat ().