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

Kai Li, Shan Lin Yang, Joseph Leung, Ba Yi Cheng

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)5857-5872
Number of pages16
JournalInternational Journal of Production Research
Volume53
Issue number19
DOIs
StatePublished - Oct 2 2015

All Science Journal Classification (ASJC) codes

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Keywords

  • Release dates
  • heuristics
  • makespan
  • resource allocation
  • scheduling
  • strongly NP-hard
  • uniform machines

Fingerprint

Dive into the research topics of 'Effective meta-heuristics for scheduling on uniform machines with resource-dependent release dates'. Together they form a unique fingerprint.

Cite this