Effective meta-heuristics for scheduling on uniform machines with resource-dependent release dates

Kai Li, Shan-lin Yang, Joseph Y.-T. Leung and Ba-yi Cheng

International Journal of Production Research, 2015, vol. 53, issue 19, 5857-5872

Abstract: This paper considers a uniform machine scheduling problem in which the release date of a job can be compressed by additional resources. The objective is to minimise the total resource usage, subject to the constraint that the makespan does not exceed a given deadline. The problem is known to be strongly NP-hard. We define two types of job moves - the right move and the left move - and analyse their effect on the resource usage. We discuss the calculation of total resource usage for two types of neighbourhood generation methods - the insertion method and exchange method. A variable neighbourhood search algorithm and a simulated annealing algorithm are developed as heuristics. To evaluate the performance of the heuristics, we develop a lower bound by relaxing the original problem to an assignment problem, which can be solved in O(n3)$ O(n^3) $ time. Finally, we generate a large number of random data, and test the performance and efficiency of the proposed heuristics. Our results indicate that the heuristics are reasonably efficient and perform very well compared with the lower bound.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2015.1012303 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:53:y:2015:i:19:p:5857-5872

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2015.1012303

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().