New lower and upper bounds for on-line scheduling

We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 1994-11, Vol.16 (4), p.221-230
Main Authors: Chen, Bo, van Vliet, André, Woeginger, Gerhard J.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Exact sciences and technology
On-line algorithms
Operational research and scientific management
Operational research. Management science
Operations research
Scheduling
Scheduling, sequencing
Worst-case analysis
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-c346t-10e627594f35eb2b3fffcb8e8351acc4acb6c22235edec6439857612ea416a23
cites cdi_FETCH-LOGICAL-c346t-10e627594f35eb2b3fffcb8e8351acc4acb6c22235edec6439857612ea416a23
container_end_page 230
container_issue 4
container_start_page 221
container_title Operations research letters
container_volume 16
creator Chen, Bo
van Vliet, André
Woeginger, Gerhard J.
description We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.
doi_str_mv 10.1016/0167-6377(94)90071-X
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_839019184</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>016763779490071X</els_id><sourcerecordid>839019184</sourcerecordid><originalsourceid>FETCH-LOGICAL-c346t-10e627594f35eb2b3fffcb8e8351acc4acb6c22235edec6439857612ea416a23</originalsourceid><addsrcrecordid>eNp9kE1LAzEQhoMoWKv_wMMeBPWwmmyy-bgIUvyCopceegvZ7EQj201Nuhb_vaktPXoY5oV53hneQeic4BuCCb_NJUpOhbhS7FphLEg5P0AjIkVVCsblIRrtkWN0ktInzpAkcoTIK6yLLqwhFqZvi2G5zKoJQ9-mwoVYhL7sfA9Fsh_QDlm-n6IjZ7oEZ7s-RrPHh9nkuZy-Pb1M7qelpYyvSoKBV6JWzNEamqqhzjnbSJC0JsZaZmzDbVVVedqC5YwqWQtOKjCMcFPRMbrcrl3G8DVAWumFTxa6zvQQhqQlVZgoIlkm2Za0MaQUwell9AsTfzTBevMfvQmvN-G1YvrvP3qebRe7AyZZ07loeuvT3ksprbFQGbvbYpCzfnuIOlkPvYXWR7Ar3Qb__51fUMZ4Ww</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>839019184</pqid></control><display><type>article</type><title>New lower and upper bounds for on-line scheduling</title><source>International Bibliography of the Social Sciences (IBSS)</source><source>ScienceDirect Journals</source><creator>Chen, Bo ; van Vliet, André ; Woeginger, Gerhard J.</creator><creatorcontrib>Chen, Bo ; van Vliet, André ; Woeginger, Gerhard J.</creatorcontrib><description>We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.</description><identifier>ISSN: 0167-6377</identifier><identifier>EISSN: 1872-7468</identifier><identifier>DOI: 10.1016/0167-6377(94)90071-X</identifier><identifier>CODEN: ORLED5</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Algorithms ; Applied sciences ; Exact sciences and technology ; On-line algorithms ; Operational research and scientific management ; Operational research. Management science ; Operations research ; Scheduling ; Scheduling, sequencing ; Worst-case analysis</subject><ispartof>Operations research letters, 1994-11, Vol.16 (4), p.221-230</ispartof><rights>1994</rights><rights>1995 INIST-CNRS</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c346t-10e627594f35eb2b3fffcb8e8351acc4acb6c22235edec6439857612ea416a23</citedby><cites>FETCH-LOGICAL-c346t-10e627594f35eb2b3fffcb8e8351acc4acb6c22235edec6439857612ea416a23</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.sciencedirect.com/science/article/pii/016763779490071X$$EHTML$$P50$$Gelsevier$$H</linktohtml><link.rule.ids>314,777,781,3427,27905,27906,33205,45972</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=3335079$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Chen, Bo</creatorcontrib><creatorcontrib>van Vliet, André</creatorcontrib><creatorcontrib>Woeginger, Gerhard J.</creatorcontrib><title>New lower and upper bounds for on-line scheduling</title><title>Operations research letters</title><description>We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.</description><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Exact sciences and technology</subject><subject>On-line algorithms</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><subject>Operations research</subject><subject>Scheduling</subject><subject>Scheduling, sequencing</subject><subject>Worst-case analysis</subject><issn>0167-6377</issn><issn>1872-7468</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1994</creationdate><recordtype>article</recordtype><sourceid>8BJ</sourceid><recordid>eNp9kE1LAzEQhoMoWKv_wMMeBPWwmmyy-bgIUvyCopceegvZ7EQj201Nuhb_vaktPXoY5oV53hneQeic4BuCCb_NJUpOhbhS7FphLEg5P0AjIkVVCsblIRrtkWN0ktInzpAkcoTIK6yLLqwhFqZvi2G5zKoJQ9-mwoVYhL7sfA9Fsh_QDlm-n6IjZ7oEZ7s-RrPHh9nkuZy-Pb1M7qelpYyvSoKBV6JWzNEamqqhzjnbSJC0JsZaZmzDbVVVedqC5YwqWQtOKjCMcFPRMbrcrl3G8DVAWumFTxa6zvQQhqQlVZgoIlkm2Za0MaQUwell9AsTfzTBevMfvQmvN-G1YvrvP3qebRe7AyZZ07loeuvT3ksprbFQGbvbYpCzfnuIOlkPvYXWR7Ar3Qb__51fUMZ4Ww</recordid><startdate>19941101</startdate><enddate>19941101</enddate><creator>Chen, Bo</creator><creator>van Vliet, André</creator><creator>Woeginger, Gerhard J.</creator><general>Elsevier B.V</general><general>Elsevier</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>8BJ</scope><scope>FQK</scope><scope>JBE</scope></search><sort><creationdate>19941101</creationdate><title>New lower and upper bounds for on-line scheduling</title><author>Chen, Bo ; van Vliet, André ; Woeginger, Gerhard J.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c346t-10e627594f35eb2b3fffcb8e8351acc4acb6c22235edec6439857612ea416a23</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1994</creationdate><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Exact sciences and technology</topic><topic>On-line algorithms</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><topic>Operations research</topic><topic>Scheduling</topic><topic>Scheduling, sequencing</topic><topic>Worst-case analysis</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Chen, Bo</creatorcontrib><creatorcontrib>van Vliet, André</creatorcontrib><creatorcontrib>Woeginger, Gerhard J.</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>International Bibliography of the Social Sciences (IBSS)</collection><collection>International Bibliography of the Social Sciences</collection><collection>International Bibliography of the Social Sciences</collection><jtitle>Operations research letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Chen, Bo</au><au>van Vliet, André</au><au>Woeginger, Gerhard J.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>New lower and upper bounds for on-line scheduling</atitle><jtitle>Operations research letters</jtitle><date>1994-11-01</date><risdate>1994</risdate><volume>16</volume><issue>4</issue><spage>221</spage><epage>230</epage><pages>221-230</pages><issn>0167-6377</issn><eissn>1872-7468</eissn><coden>ORLED5</coden><abstract>We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/0167-6377(94)90071-X</doi><tpages>10</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0167-6377
ispartof Operations research letters, 1994-11, Vol.16 (4), p.221-230
issn 0167-6377
1872-7468
language eng
recordid cdi_proquest_miscellaneous_839019184
source International Bibliography of the Social Sciences (IBSS); ScienceDirect Journals
subjects Algorithms
Applied sciences
Exact sciences and technology
On-line algorithms
Operational research and scientific management
Operational research. Management science
Operations research
Scheduling
Scheduling, sequencing
Worst-case analysis
title New lower and upper bounds for on-line scheduling
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-20T18%3A00%3A51IST&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=New%20lower%20and%20upper%20bounds%20for%20on-line%20scheduling&rft.jtitle=Operations%20research%20letters&rft.au=Chen,%20Bo&rft.date=1994-11-01&rft.volume=16&rft.issue=4&rft.spage=221&rft.epage=230&rft.pages=221-230&rft.issn=0167-6377&rft.eissn=1872-7468&rft.coden=ORLED5&rft_id=info:doi/10.1016/0167-6377(94)90071-X&rft_dat=%3Cproquest_cross%3E839019184%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c346t-10e627594f35eb2b3fffcb8e8351acc4acb6c22235edec6439857612ea416a23%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=839019184&rft_id=info:pmid/&rfr_iscdi=true