Single‐machine scheduling problem with resource dependent release dates to minimise total resource‐consumption

Kai Li, Shan-Lin Yang and Ming-Lun Ren

International Journal of Systems Science, 2011, vol. 42, issue 10, 1811-1820

Abstract: This article considers the single‐machine scheduling problem to minimise the total resource consumption under the constraint that the makespan does not exceed a given limit, in which the release date of a job is a linear decreasing continuous function of the resource consumption. This problem is NP-hard in the strong sense. We design a simulated annealing (SA) algorithm to obtain the near-optimal solution with high quality. Two operators, right-move and left-move, are defined and their influences on the resource consumption are analysed. We use two operations, insert and swap, to generate the neighbourhood, and discuss how to calculate the change of total resource consumption. To evaluate the performance of the proposed algorithm, we relax the problem to an assignment problem, and obtain a lower bound by the Hungary method. And then, we improve its quality by Chu's method. Based on the settings that Janiak provided, we generate the random test data in our experiments to simulate the ingot preheating and hot-rolling process in steel mills. The accuracy and efficiency of the proposed SA algorithm are tested based on those data with problem sizes varying from 50 to 200 jobs. The computational results indicate that the SA approach is promising and capable of solving large-scale problems in a reasonable time.

Date: 2011
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207721003653716 (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:tsysxx:v:42:y:2011:i:10:p:1811-1820

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

DOI: 10.1080/00207721003653716

Access Statistics for this article

International Journal of Systems Science is currently edited by Visakan Kadirkamanathan

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