Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness

Arne Mensendiek, Jatinder N.D. Gupta and Jan Herrmann

European Journal of Operational Research, 2015, vol. 243, issue 2, 514-522

Abstract: This paper addresses the problem of minimizing the total tardiness of a set of jobs to be scheduled on identical parallel machines where jobs can only be delivered at certain fixed delivery dates. Scheduling problems with fixed delivery dates are frequent in industry, for example when a manufacturer has to rely on the timetable of a logistics provider to ship its products to customers. We develop and empirically evaluate both optimal and heuristic solution procedures to solve the problem. As the problem is NP-hard, only relatively small instances can be optimally solved in reasonable computational time using either an efficient mathematical programming formulation or a branch-and-bound algorithm. Consequently, we develop a tabu search and a hybrid genetic algorithm to quickly find good approximate solutions for larger instances.

Keywords: Scheduling; Assignment problems; Branch and bound; Metaheuristics; Fixed delivery dates (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714009849
Full text for ScienceDirect subscribers only

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:eee:ejores:v:243:y:2015:i:2:p:514-522

DOI: 10.1016/j.ejor.2014.12.002

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().