Interval scheduling: A survey

In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability o...

Full description

Saved in:
Bibliographic Details
Published in:Naval research logistics 2007-08, Vol.54 (5), p.530-543
Main Authors: Kolen, Antoon W.J., Lenstra, Jan Karel, Papadimitriou, Christos H., Spieksma, Frits C.R.
Format: Article
Language:English
Subjects:
analysis of algorithms
computational complexity: exact algorithms
deterministic: interval scheduling
production/scheduling
sequencing
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-c4931-2486bc5352e72579c9cba63c4fa99b205321d05ce95f72f81799e84e17036cd63
cites cdi_FETCH-LOGICAL-c4931-2486bc5352e72579c9cba63c4fa99b205321d05ce95f72f81799e84e17036cd63
container_end_page 543
container_issue 5
container_start_page 530
container_title Naval research logistics
container_volume 54
creator Kolen, Antoon W.J.
Lenstra, Jan Karel
Papadimitriou, Christos H.
Spieksma, Frits C.R.
description In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given “maximal” machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007
doi_str_mv 10.1002/nav.20231
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_30052236</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>30052236</sourcerecordid><originalsourceid>FETCH-LOGICAL-c4931-2486bc5352e72579c9cba63c4fa99b205321d05ce95f72f81799e84e17036cd63</originalsourceid><addsrcrecordid>eNp1kDFPAjEYhhujiYgO_gATJhOHg6_ttb26AVEkQVwU2ZpSvtPT44D2DuXfC566Ob3L87zDQ8g5hTYFYJ3CbtoMGKcHpEEFg0gqAYekAYmOI5B6ekxOQngDABmDaJCLYVGi39i8Fdwrzqs8K16uW91WqPwGt6fkKLV5wLOfbZKn25vH_l00ehgM-91R5GLNacTiRM6c4IKhYkJpp93MSu7i1Go9YyA4o3MQDrVIFUsTqrTGJEaqgEs3l7xJLuvflV-uKwylWWTBYZ7bApdVMBxAMMb34FUNOr8MwWNqVj5bWL81FMw-gNkFMN8BdmynZj-yHLf_g2bcnfwaUW1kocTPP8P6dyMVV8I8jwdmOhG9HtyPzIR_AaBEaTk</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>30052236</pqid></control><display><type>article</type><title>Interval scheduling: A survey</title><source>Wiley</source><creator>Kolen, Antoon W.J. ; Lenstra, Jan Karel ; Papadimitriou, Christos H. ; Spieksma, Frits C.R.</creator><creatorcontrib>Kolen, Antoon W.J. ; Lenstra, Jan Karel ; Papadimitriou, Christos H. ; Spieksma, Frits C.R.</creatorcontrib><description>In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given “maximal” machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007</description><identifier>ISSN: 0894-069X</identifier><identifier>EISSN: 1520-6750</identifier><identifier>DOI: 10.1002/nav.20231</identifier><language>eng</language><publisher>Hoboken: Wiley Subscription Services, Inc., A Wiley Company</publisher><subject>analysis of algorithms ; computational complexity: exact algorithms ; deterministic: interval scheduling ; production/scheduling ; sequencing</subject><ispartof>Naval research logistics, 2007-08, Vol.54 (5), p.530-543</ispartof><rights>Copyright © 2007 Wiley Periodicals, Inc.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c4931-2486bc5352e72579c9cba63c4fa99b205321d05ce95f72f81799e84e17036cd63</citedby><cites>FETCH-LOGICAL-c4931-2486bc5352e72579c9cba63c4fa99b205321d05ce95f72f81799e84e17036cd63</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27922,27923</link.rule.ids></links><search><creatorcontrib>Kolen, Antoon W.J.</creatorcontrib><creatorcontrib>Lenstra, Jan Karel</creatorcontrib><creatorcontrib>Papadimitriou, Christos H.</creatorcontrib><creatorcontrib>Spieksma, Frits C.R.</creatorcontrib><title>Interval scheduling: A survey</title><title>Naval research logistics</title><addtitle>Naval Research Logistics</addtitle><description>In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given “maximal” machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007</description><subject>analysis of algorithms</subject><subject>computational complexity: exact algorithms</subject><subject>deterministic: interval scheduling</subject><subject>production/scheduling</subject><subject>sequencing</subject><issn>0894-069X</issn><issn>1520-6750</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2007</creationdate><recordtype>article</recordtype><recordid>eNp1kDFPAjEYhhujiYgO_gATJhOHg6_ttb26AVEkQVwU2ZpSvtPT44D2DuXfC566Ob3L87zDQ8g5hTYFYJ3CbtoMGKcHpEEFg0gqAYekAYmOI5B6ekxOQngDABmDaJCLYVGi39i8Fdwrzqs8K16uW91WqPwGt6fkKLV5wLOfbZKn25vH_l00ehgM-91R5GLNacTiRM6c4IKhYkJpp93MSu7i1Go9YyA4o3MQDrVIFUsTqrTGJEaqgEs3l7xJLuvflV-uKwylWWTBYZ7bApdVMBxAMMb34FUNOr8MwWNqVj5bWL81FMw-gNkFMN8BdmynZj-yHLf_g2bcnfwaUW1kocTPP8P6dyMVV8I8jwdmOhG9HtyPzIR_AaBEaTk</recordid><startdate>200708</startdate><enddate>200708</enddate><creator>Kolen, Antoon W.J.</creator><creator>Lenstra, Jan Karel</creator><creator>Papadimitriou, Christos H.</creator><creator>Spieksma, Frits C.R.</creator><general>Wiley Subscription Services, Inc., A Wiley Company</general><scope>BSCLL</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7TB</scope><scope>8FD</scope><scope>FR3</scope><scope>JQ2</scope><scope>KR7</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>200708</creationdate><title>Interval scheduling: A survey</title><author>Kolen, Antoon W.J. ; Lenstra, Jan Karel ; Papadimitriou, Christos H. ; Spieksma, Frits C.R.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c4931-2486bc5352e72579c9cba63c4fa99b205321d05ce95f72f81799e84e17036cd63</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2007</creationdate><topic>analysis of algorithms</topic><topic>computational complexity: exact algorithms</topic><topic>deterministic: interval scheduling</topic><topic>production/scheduling</topic><topic>sequencing</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Kolen, Antoon W.J.</creatorcontrib><creatorcontrib>Lenstra, Jan Karel</creatorcontrib><creatorcontrib>Papadimitriou, Christos H.</creatorcontrib><creatorcontrib>Spieksma, Frits C.R.</creatorcontrib><collection>Istex</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>Technology Research Database</collection><collection>Engineering Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Civil Engineering Abstracts</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Naval research logistics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Kolen, Antoon W.J.</au><au>Lenstra, Jan Karel</au><au>Papadimitriou, Christos H.</au><au>Spieksma, Frits C.R.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Interval scheduling: A survey</atitle><jtitle>Naval research logistics</jtitle><addtitle>Naval Research Logistics</addtitle><date>2007-08</date><risdate>2007</risdate><volume>54</volume><issue>5</issue><spage>530</spage><epage>543</epage><pages>530-543</pages><issn>0894-069X</issn><eissn>1520-6750</eissn><abstract>In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given “maximal” machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007</abstract><cop>Hoboken</cop><pub>Wiley Subscription Services, Inc., A Wiley Company</pub><doi>10.1002/nav.20231</doi><tpages>14</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0894-069X
ispartof Naval research logistics, 2007-08, Vol.54 (5), p.530-543
issn 0894-069X
1520-6750
language eng
recordid cdi_proquest_miscellaneous_30052236
source Wiley
subjects analysis of algorithms
computational complexity: exact algorithms
deterministic: interval scheduling
production/scheduling
sequencing
title Interval scheduling: A survey
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-09T12%3A22%3A47IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Interval%20scheduling:%20A%20survey&rft.jtitle=Naval%20research%20logistics&rft.au=Kolen,%20Antoon%20W.J.&rft.date=2007-08&rft.volume=54&rft.issue=5&rft.spage=530&rft.epage=543&rft.pages=530-543&rft.issn=0894-069X&rft.eissn=1520-6750&rft_id=info:doi/10.1002/nav.20231&rft_dat=%3Cproquest_cross%3E30052236%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c4931-2486bc5352e72579c9cba63c4fa99b205321d05ce95f72f81799e84e17036cd63%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=30052236&rft_id=info:pmid/&rfr_iscdi=true