Single-machine scheduling with time window-dependent processing times

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

Full description

Saved in:
Bibliographic Details
Published in:The Journal of the Operational Research Society 2006-02, Vol.57 (2), p.133-139
Main Authors: Lahlou, C, Dauzère-Pérès, S
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computational Complexity
Computer Science
Exact sciences and technology
Integers
Job shops
Mathematical models
Modeling
one-machine
Operational research and scientific management
Operational research. Management science
Operations Research
Polynomials
Production scheduling
Schedules
Scheduling
Scheduling, sequencing
Sequential scheduling
Studies
Theoretical Papers
Time dependence
Time windows
time-dependent processing time
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c469t-5e563aacce92f804e254bdf24f8aad43b6f421332578c0e84685b17b1ac25be63
cites cdi_FETCH-LOGICAL-c469t-5e563aacce92f804e254bdf24f8aad43b6f421332578c0e84685b17b1ac25be63
container_end_page 139
container_issue 2
container_start_page 133
container_title The Journal of the Operational Research Society
container_volume 57
creator Lahlou, C
Dauzère-Pérès, S
description 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.
doi_str_mv 10.1057/palgrave.jors.2601931
format article
fullrecord <record><control><sourceid>jstor_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1057_palgrave_jors_2601931</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><jstor_id>4102281</jstor_id><sourcerecordid>4102281</sourcerecordid><originalsourceid>FETCH-LOGICAL-c469t-5e563aacce92f804e254bdf24f8aad43b6f421332578c0e84685b17b1ac25be63</originalsourceid><addsrcrecordid>eNp9kE1L5EAQhptFYUfdf7ALg7CHPWSs_kxyU8RVYcCDem4qnYqTIZOe7c44-O_tkNG9eeqm6qmHl5exXxwWHHR-scXuJeArLdY-xIUwwEvJv7EZV7nJSmngiM2AG8i0KcR3dhLjGgDKhM3YzWPbv3SUbdCt2p7m0a2o3nVpON-3w2o-tBtKv772-6ymLfU19cN8G7yjGEdqBOIZO26wi_Tj8J6y5783T9d32fLh9v76apk5Zcoh06SNRHSOStEUoEhoVdWNUE2BWCtZmUYJLqXQeeGACmUKXfG84uiErsjIU_Zn8q6ws9vQbjC8WY-tvbta2nEGII0EBa88secTm8L-21Ec7NrvQp_iWSG5zE0JKkF6glzwMQZqPq0c7Fiu_SjXjuXaQ7np7vdBjtFh1wTsXRv_H-cGciFF4n5O3DoOPnzuFQchilFzOa3bvvFhg3sfutoO-Nb58OGUXyd5B1aTnbo</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>231376904</pqid></control><display><type>article</type><title>Single-machine scheduling with time window-dependent processing times</title><source>ABI/INFORM Global (ProQuest)</source><source>JSTOR Archival Journals and Primary Sources Collection</source><source>Taylor and Francis Science and Technology Collection</source><creator>Lahlou, C ; Dauzère-Pérès, S</creator><creatorcontrib>Lahlou, C ; Dauzère-Pérès, S</creatorcontrib><description>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.</description><identifier>ISSN: 0160-5682</identifier><identifier>EISSN: 1476-9360</identifier><identifier>EISSN: 0160-5682</identifier><identifier>DOI: 10.1057/palgrave.jors.2601931</identifier><identifier>CODEN: JORSDZ</identifier><language>eng</language><publisher>Basingstoke: Taylor &amp; Francis</publisher><subject>Algorithms ; Applied sciences ; Computational Complexity ; Computer Science ; Exact sciences and technology ; Integers ; Job shops ; Mathematical models ; Modeling ; one-machine ; Operational research and scientific management ; Operational research. Management science ; Operations Research ; Polynomials ; Production scheduling ; Schedules ; Scheduling ; Scheduling, sequencing ; Sequential scheduling ; Studies ; Theoretical Papers ; Time dependence ; Time windows ; time-dependent processing time</subject><ispartof>The Journal of the Operational Research Society, 2006-02, Vol.57 (2), p.133-139</ispartof><rights>Copyright © 2005, Palgrave Macmillan Ltd 2005</rights><rights>Copyright 2006 Operational Research Society Ltd</rights><rights>2006 INIST-CNRS</rights><rights>Palgrave Macmillan Ltd 2006</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c469t-5e563aacce92f804e254bdf24f8aad43b6f421332578c0e84685b17b1ac25be63</citedby><cites>FETCH-LOGICAL-c469t-5e563aacce92f804e254bdf24f8aad43b6f421332578c0e84685b17b1ac25be63</cites><orcidid>0000-0002-3875-5877</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/231376904/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/231376904?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>230,314,780,784,885,11687,27923,27924,36059,44362,58237,58470,74766</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=17607232$$DView record in Pascal Francis$$Hfree_for_read</backlink><backlink>$$Uhttps://hal.science/hal-00363040$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Lahlou, C</creatorcontrib><creatorcontrib>Dauzère-Pérès, S</creatorcontrib><title>Single-machine scheduling with time window-dependent processing times</title><title>The Journal of the Operational Research Society</title><description>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.</description><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Computational Complexity</subject><subject>Computer Science</subject><subject>Exact sciences and technology</subject><subject>Integers</subject><subject>Job shops</subject><subject>Mathematical models</subject><subject>Modeling</subject><subject>one-machine</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><subject>Operations Research</subject><subject>Polynomials</subject><subject>Production scheduling</subject><subject>Schedules</subject><subject>Scheduling</subject><subject>Scheduling, sequencing</subject><subject>Sequential scheduling</subject><subject>Studies</subject><subject>Theoretical Papers</subject><subject>Time dependence</subject><subject>Time windows</subject><subject>time-dependent processing time</subject><issn>0160-5682</issn><issn>1476-9360</issn><issn>0160-5682</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2006</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp9kE1L5EAQhptFYUfdf7ALg7CHPWSs_kxyU8RVYcCDem4qnYqTIZOe7c44-O_tkNG9eeqm6qmHl5exXxwWHHR-scXuJeArLdY-xIUwwEvJv7EZV7nJSmngiM2AG8i0KcR3dhLjGgDKhM3YzWPbv3SUbdCt2p7m0a2o3nVpON-3w2o-tBtKv772-6ymLfU19cN8G7yjGEdqBOIZO26wi_Tj8J6y5783T9d32fLh9v76apk5Zcoh06SNRHSOStEUoEhoVdWNUE2BWCtZmUYJLqXQeeGACmUKXfG84uiErsjIU_Zn8q6ws9vQbjC8WY-tvbta2nEGII0EBa88secTm8L-21Ec7NrvQp_iWSG5zE0JKkF6glzwMQZqPq0c7Fiu_SjXjuXaQ7np7vdBjtFh1wTsXRv_H-cGciFF4n5O3DoOPnzuFQchilFzOa3bvvFhg3sfutoO-Nb58OGUXyd5B1aTnbo</recordid><startdate>20060201</startdate><enddate>20060201</enddate><creator>Lahlou, C</creator><creator>Dauzère-Pérès, S</creator><general>Taylor &amp; Francis</general><general>Palgrave Macmillan Press</general><general>Palgrave</general><general>Taylor &amp; Francis Ltd</general><general>Palgrave Macmillan</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>0U~</scope><scope>1-H</scope><scope>3V.</scope><scope>7RQ</scope><scope>7WY</scope><scope>7WZ</scope><scope>7X7</scope><scope>7XB</scope><scope>87Z</scope><scope>88E</scope><scope>8AL</scope><scope>8FE</scope><scope>8FG</scope><scope>8FI</scope><scope>8FJ</scope><scope>8FK</scope><scope>8FL</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>FYUFA</scope><scope>F~G</scope><scope>GHDGH</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>K9.</scope><scope>L.-</scope><scope>L.0</scope><scope>L6V</scope><scope>M0C</scope><scope>M0N</scope><scope>M0S</scope><scope>M1P</scope><scope>M2O</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope><scope>U9A</scope><scope>1XC</scope><scope>VOOES</scope><orcidid>https://orcid.org/0000-0002-3875-5877</orcidid></search><sort><creationdate>20060201</creationdate><title>Single-machine scheduling with time window-dependent processing times</title><author>Lahlou, C ; Dauzère-Pérès, S</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c469t-5e563aacce92f804e254bdf24f8aad43b6f421332578c0e84685b17b1ac25be63</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2006</creationdate><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Computational Complexity</topic><topic>Computer Science</topic><topic>Exact sciences and technology</topic><topic>Integers</topic><topic>Job shops</topic><topic>Mathematical models</topic><topic>Modeling</topic><topic>one-machine</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><topic>Operations Research</topic><topic>Polynomials</topic><topic>Production scheduling</topic><topic>Schedules</topic><topic>Scheduling</topic><topic>Scheduling, sequencing</topic><topic>Sequential scheduling</topic><topic>Studies</topic><topic>Theoretical Papers</topic><topic>Time dependence</topic><topic>Time windows</topic><topic>time-dependent processing time</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Lahlou, C</creatorcontrib><creatorcontrib>Dauzère-Pérès, S</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Global News &amp; ABI/Inform Professional</collection><collection>Trade PRO</collection><collection>ProQuest Central (Corporate)</collection><collection>ProQuest Career &amp; Technical Education Database</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Health &amp; Medical Collection</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Medical Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Hospital Premium Collection</collection><collection>Hospital Premium Collection (Alumni Edition)</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Database (Proquest)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>Business Premium Collection (Alumni)</collection><collection>Health Research Premium Collection</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>Health Research Premium Collection (Alumni)</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ProQuest Health &amp; Medical Complete (Alumni)</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ABI/INFORM Professional Standard</collection><collection>ProQuest Engineering Collection</collection><collection>ABI/INFORM Global (ProQuest)</collection><collection>Computing Database</collection><collection>Health &amp; Medical Collection (Alumni Edition)</collection><collection>Medical Database</collection><collection>ProQuest Research Library</collection><collection>Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>ProQuest Central Basic</collection><collection>Hyper Article en Ligne (HAL)</collection><collection>Hyper Article en Ligne (HAL) (Open Access)</collection><jtitle>The Journal of the Operational Research Society</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Lahlou, C</au><au>Dauzère-Pérès, S</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Single-machine scheduling with time window-dependent processing times</atitle><jtitle>The Journal of the Operational Research Society</jtitle><date>2006-02-01</date><risdate>2006</risdate><volume>57</volume><issue>2</issue><spage>133</spage><epage>139</epage><pages>133-139</pages><issn>0160-5682</issn><eissn>1476-9360</eissn><eissn>0160-5682</eissn><coden>JORSDZ</coden><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.</abstract><cop>Basingstoke</cop><pub>Taylor &amp; Francis</pub><doi>10.1057/palgrave.jors.2601931</doi><tpages>7</tpages><orcidid>https://orcid.org/0000-0002-3875-5877</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0160-5682
ispartof The Journal of the Operational Research Society, 2006-02, Vol.57 (2), p.133-139
issn 0160-5682
1476-9360
0160-5682
language eng
recordid cdi_crossref_primary_10_1057_palgrave_jors_2601931
source ABI/INFORM Global (ProQuest); JSTOR Archival Journals and Primary Sources Collection; Taylor and Francis Science and Technology Collection
subjects Algorithms
Applied sciences
Computational Complexity
Computer Science
Exact sciences and technology
Integers
Job shops
Mathematical models
Modeling
one-machine
Operational research and scientific management
Operational research. Management science
Operations Research
Polynomials
Production scheduling
Schedules
Scheduling
Scheduling, sequencing
Sequential scheduling
Studies
Theoretical Papers
Time dependence
Time windows
time-dependent processing time
title Single-machine scheduling with time window-dependent processing times
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T17%3A53%3A03IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-jstor_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Single-machine%20scheduling%20with%20time%20window-dependent%20processing%20times&rft.jtitle=The%20Journal%20of%20the%20Operational%20Research%20Society&rft.au=Lahlou,%20C&rft.date=2006-02-01&rft.volume=57&rft.issue=2&rft.spage=133&rft.epage=139&rft.pages=133-139&rft.issn=0160-5682&rft.eissn=1476-9360&rft.coden=JORSDZ&rft_id=info:doi/10.1057/palgrave.jors.2601931&rft_dat=%3Cjstor_cross%3E4102281%3C/jstor_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c469t-5e563aacce92f804e254bdf24f8aad43b6f421332578c0e84685b17b1ac25be63%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=231376904&rft_id=info:pmid/&rft_jstor_id=4102281&rfr_iscdi=true