A single machine scheduling problem with two-dimensional vector packing constraints

Jean-Charles Billaut, Federico Della Croce and Andrea Grosso

European Journal of Operational Research, 2015, vol. 243, issue 1, 75-81

Abstract: We consider a scheduling problem where jobs consume a perishable resource stored in vials. It leads to a new scheduling problem, with two-dimensional jobs, one dimension for the duration and one dimension for the consumption. Jobs have to be finished before a given due date, and the objective is to schedule the jobs on a single machine so that the maximum lateness does not exceed a given threshold and the number of vials required for processing all the jobs is minimized. We propose a two-step approach embedding a Recovering Beam Search algorithm to get a good-quality initial solution reachable in short time and a more time consuming matheuristic algorithm. Computational experiments are performed on the benchmark instances available for the two-dimensional vector packing problem integrated with additional due dates to take into account the maximum lateness constraints. The computational results show very good performances of the proposed approach that remains effective also on the original two-dimensional vector packing instances without due dates where 7 new bounds are obtained.

Keywords: Scheduling; Two-dimensional vector packing; Recovering beam search; Matheuristics (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171400959X
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:1:p:75-81

DOI: 10.1016/j.ejor.2014.11.036

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 ().