Single-machine scheduling with time window-dependent processing times

C Lahlou () and S Dauzère-Pérès
Additional contact information
C Lahlou: IRCCyN—Ecole des Mines de Nantes
S Dauzère-Pérès: Ecole des Mines de Saint-Etienne

Journal of the Operational Research Society, 2006, vol. 57, issue 2, 133-139

Abstract: Abstract In the one-machine scheduling problems analysed in this paper, the processing time of a job depends on the time at which the job is started. More precisely, the horizon is divided into time windows and with each one a coefficient is associated that is used to determine the actual processing time of a job starting in it. Two models are introduced, and one of them has direct connections with models considered in previous papers on scheduling problems with time-dependent processing times. Various computational complexity results are presented for the makespan criterion, which show that the problem is NP-hard, even with two time windows. Solving procedures are also proposed for some special cases.

Keywords: scheduling; one-machine; time-dependent processing time; time windows; computational complexity (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601931 Abstract (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:pal:jorsoc:v:57:y:2006:i:2:d:10.1057_palgrave.jors.2601931

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601931

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().