Loading…
Tight lower bounds for semi-online scheduling on two uniform machines with known optimum
This problem is about scheduling a number of jobs on two uniform machines with given speeds 1 and s ≥ 1 , so that the overall finishing time, i.e., the makespan, is earliest possible. We consider a semi-online variant (introduced for equal speeds) by Azar and Regev, where the jobs are arriving one a...
Saved in:
| Published in: | Central European journal of operations research 2019-12, Vol.27 (4), p.1107-1130 |
|---|---|
| Main Authors: | , , , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| 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-c500t-6e4063738d590877f1cd45adce0deb9812d5488a185cec5e626aaa650a4fee1c3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c500t-6e4063738d590877f1cd45adce0deb9812d5488a185cec5e626aaa650a4fee1c3 |
| container_end_page | 1130 |
| container_issue | 4 |
| container_start_page | 1107 |
| container_title | Central European journal of operations research |
| container_volume | 27 |
| creator | Dósa, György Fügenschuh, Armin Tan, Zhiyi Tuza, Zsolt Węsek, Krzysztof |
| description | This problem is about scheduling a number of jobs on two uniform machines with given speeds 1 and
s
≥
1
, so that the overall finishing time, i.e., the makespan, is earliest possible. We consider a semi-online variant (introduced for equal speeds) by Azar and Regev, where the jobs are arriving one after the other, while the scheduling algorithm knows the optimum value of the corresponding offline problem. One can ask how close any possible algorithm could get to the optimum value, that is, to give a lower bound on the competitive ratio: the supremum over ratios between the value of the solution given by the algorithm and the optimal offline solution. We contribute to this question by constructing tight lower bounds for all values of
s
in the intervals
[
1
+
21
4
,
3
+
73
8
]
≈
[
1.3956
,
1.443
]
and
[
5
3
,
4
+
133
9
]
≈
[
5
3
,
1.7258
]
, except a very narrow interval. |
| doi_str_mv | 10.1007/s10100-018-0536-9 |
| format | article |
| fullrecord | <record><control><sourceid>gale_proqu</sourceid><recordid>TN_cdi_proquest_journals_2022075271</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A706498816</galeid><sourcerecordid>A706498816</sourcerecordid><originalsourceid>FETCH-LOGICAL-c500t-6e4063738d590877f1cd45adce0deb9812d5488a185cec5e626aaa650a4fee1c3</originalsourceid><addsrcrecordid>eNp1kcFq3DAQhk1JoUnaB-hNkGuVjGRLlo8hNGkh0EsKuQmtPPYqXUsbjc2St68WB9IegmBmGL5_pNFfVV8FXAqA9ooElMxBGA6q1rz7UJ0KLWreidaclLqpFZeNfvxUnRE9AUjRgT6tHh_CuJ3ZLh0ws01aYk9sSJkRToGnuAsRGfkt9kspR5Yimw-JLTEUaGKT89tCEDuEecv-xHSILO3nMC3T5-rj4HaEX17zefX79vvDzQ9-_-vu5831PfcKYOYaG9B1W5tedWDadhC-b5TrPUKPm84I2avGGCeM8ugVaqmdc1qBawZE4evz6mKdu8_peUGa7VNacixXWglSQqtkKwp1uVKj26ENcUhzdr6cvuzpU8QhlP51C7rpjBG6CL79I9gsdFyzBDp-F41uIfofFyvucyLKONh9DpPLL1aAPRpkV4NsMcgeDbJd0chVQ4WNI-a3l78v-gu0TJN5</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2022075271</pqid></control><display><type>article</type><title>Tight lower bounds for semi-online scheduling on two uniform machines with known optimum</title><source>Business Source Ultimate【Trial: -2024/12/31】【Remote access available】</source><source>ABI/INFORM Global</source><source>Springer Nature</source><creator>Dósa, György ; Fügenschuh, Armin ; Tan, Zhiyi ; Tuza, Zsolt ; Węsek, Krzysztof</creator><creatorcontrib>Dósa, György ; Fügenschuh, Armin ; Tan, Zhiyi ; Tuza, Zsolt ; Węsek, Krzysztof</creatorcontrib><description>This problem is about scheduling a number of jobs on two uniform machines with given speeds 1 and
s
≥
1
, so that the overall finishing time, i.e., the makespan, is earliest possible. We consider a semi-online variant (introduced for equal speeds) by Azar and Regev, where the jobs are arriving one after the other, while the scheduling algorithm knows the optimum value of the corresponding offline problem. One can ask how close any possible algorithm could get to the optimum value, that is, to give a lower bound on the competitive ratio: the supremum over ratios between the value of the solution given by the algorithm and the optimal offline solution. We contribute to this question by constructing tight lower bounds for all values of
s
in the intervals
[
1
+
21
4
,
3
+
73
8
]
≈
[
1.3956
,
1.443
]
and
[
5
3
,
4
+
133
9
]
≈
[
5
3
,
1.7258
]
, except a very narrow interval.</description><identifier>ISSN: 1435-246X</identifier><identifier>EISSN: 1613-9178</identifier><identifier>DOI: 10.1007/s10100-018-0536-9</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer Berlin Heidelberg</publisher><subject>Algorithms ; Business and Management ; Lower bounds ; Machinery ; Magneto-electric machines ; Mathematical optimization ; Methods ; Operations research ; Operations Research/Decision Theory ; Optimization ; Original Paper ; Production scheduling ; Scheduling ; Scheduling (Management) ; Scheduling algorithms</subject><ispartof>Central European journal of operations research, 2019-12, Vol.27 (4), p.1107-1130</ispartof><rights>Springer-Verlag GmbH Germany, part of Springer Nature 2018</rights><rights>COPYRIGHT 2019 Springer</rights><rights>Central European Journal of Operations Research is a copyright of Springer, (2018). All Rights Reserved.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c500t-6e4063738d590877f1cd45adce0deb9812d5488a185cec5e626aaa650a4fee1c3</citedby><cites>FETCH-LOGICAL-c500t-6e4063738d590877f1cd45adce0deb9812d5488a185cec5e626aaa650a4fee1c3</cites><orcidid>0000-0003-3637-4066</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2022075271/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2022075271?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11688,27924,27925,36060,44363,74895</link.rule.ids></links><search><creatorcontrib>Dósa, György</creatorcontrib><creatorcontrib>Fügenschuh, Armin</creatorcontrib><creatorcontrib>Tan, Zhiyi</creatorcontrib><creatorcontrib>Tuza, Zsolt</creatorcontrib><creatorcontrib>Węsek, Krzysztof</creatorcontrib><title>Tight lower bounds for semi-online scheduling on two uniform machines with known optimum</title><title>Central European journal of operations research</title><addtitle>Cent Eur J Oper Res</addtitle><description>This problem is about scheduling a number of jobs on two uniform machines with given speeds 1 and
s
≥
1
, so that the overall finishing time, i.e., the makespan, is earliest possible. We consider a semi-online variant (introduced for equal speeds) by Azar and Regev, where the jobs are arriving one after the other, while the scheduling algorithm knows the optimum value of the corresponding offline problem. One can ask how close any possible algorithm could get to the optimum value, that is, to give a lower bound on the competitive ratio: the supremum over ratios between the value of the solution given by the algorithm and the optimal offline solution. We contribute to this question by constructing tight lower bounds for all values of
s
in the intervals
[
1
+
21
4
,
3
+
73
8
]
≈
[
1.3956
,
1.443
]
and
[
5
3
,
4
+
133
9
]
≈
[
5
3
,
1.7258
]
, except a very narrow interval.</description><subject>Algorithms</subject><subject>Business and Management</subject><subject>Lower bounds</subject><subject>Machinery</subject><subject>Magneto-electric machines</subject><subject>Mathematical optimization</subject><subject>Methods</subject><subject>Operations research</subject><subject>Operations Research/Decision Theory</subject><subject>Optimization</subject><subject>Original Paper</subject><subject>Production scheduling</subject><subject>Scheduling</subject><subject>Scheduling (Management)</subject><subject>Scheduling algorithms</subject><issn>1435-246X</issn><issn>1613-9178</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2019</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kcFq3DAQhk1JoUnaB-hNkGuVjGRLlo8hNGkh0EsKuQmtPPYqXUsbjc2St68WB9IegmBmGL5_pNFfVV8FXAqA9ooElMxBGA6q1rz7UJ0KLWreidaclLqpFZeNfvxUnRE9AUjRgT6tHh_CuJ3ZLh0ws01aYk9sSJkRToGnuAsRGfkt9kspR5Yimw-JLTEUaGKT89tCEDuEecv-xHSILO3nMC3T5-rj4HaEX17zefX79vvDzQ9-_-vu5831PfcKYOYaG9B1W5tedWDadhC-b5TrPUKPm84I2avGGCeM8ugVaqmdc1qBawZE4evz6mKdu8_peUGa7VNacixXWglSQqtkKwp1uVKj26ENcUhzdr6cvuzpU8QhlP51C7rpjBG6CL79I9gsdFyzBDp-F41uIfofFyvucyLKONh9DpPLL1aAPRpkV4NsMcgeDbJd0chVQ4WNI-a3l78v-gu0TJN5</recordid><startdate>20191201</startdate><enddate>20191201</enddate><creator>Dósa, György</creator><creator>Fügenschuh, Armin</creator><creator>Tan, Zhiyi</creator><creator>Tuza, Zsolt</creator><creator>Węsek, Krzysztof</creator><general>Springer Berlin Heidelberg</general><general>Springer</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>N95</scope><scope>3V.</scope><scope>7SC</scope><scope>7TB</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</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>FR3</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>H8D</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>KR7</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M7S</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><orcidid>https://orcid.org/0000-0003-3637-4066</orcidid></search><sort><creationdate>20191201</creationdate><title>Tight lower bounds for semi-online scheduling on two uniform machines with known optimum</title><author>Dósa, György ; Fügenschuh, Armin ; Tan, Zhiyi ; Tuza, Zsolt ; Węsek, Krzysztof</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c500t-6e4063738d590877f1cd45adce0deb9812d5488a185cec5e626aaa650a4fee1c3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2019</creationdate><topic>Algorithms</topic><topic>Business and Management</topic><topic>Lower bounds</topic><topic>Machinery</topic><topic>Magneto-electric machines</topic><topic>Mathematical optimization</topic><topic>Methods</topic><topic>Operations research</topic><topic>Operations Research/Decision Theory</topic><topic>Optimization</topic><topic>Original Paper</topic><topic>Production scheduling</topic><topic>Scheduling</topic><topic>Scheduling (Management)</topic><topic>Scheduling algorithms</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Dósa, György</creatorcontrib><creatorcontrib>Fügenschuh, Armin</creatorcontrib><creatorcontrib>Tan, Zhiyi</creatorcontrib><creatorcontrib>Tuza, Zsolt</creatorcontrib><creatorcontrib>Węsek, Krzysztof</creatorcontrib><collection>CrossRef</collection><collection>Gale_Business Insights: Global</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical & Transportation Engineering Abstracts</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Global (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science & Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies & Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>Engineering Research Database</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>Aerospace Database</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>Civil Engineering Abstracts</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Global</collection><collection>Computing Database</collection><collection>Engineering Database</collection><collection>Advanced Technologies & Aerospace Database</collection><collection>ProQuest Advanced Technologies & Aerospace Collection</collection><collection>ProQuest One Business</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><jtitle>Central European journal of operations research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Dósa, György</au><au>Fügenschuh, Armin</au><au>Tan, Zhiyi</au><au>Tuza, Zsolt</au><au>Węsek, Krzysztof</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Tight lower bounds for semi-online scheduling on two uniform machines with known optimum</atitle><jtitle>Central European journal of operations research</jtitle><stitle>Cent Eur J Oper Res</stitle><date>2019-12-01</date><risdate>2019</risdate><volume>27</volume><issue>4</issue><spage>1107</spage><epage>1130</epage><pages>1107-1130</pages><issn>1435-246X</issn><eissn>1613-9178</eissn><abstract>This problem is about scheduling a number of jobs on two uniform machines with given speeds 1 and
s
≥
1
, so that the overall finishing time, i.e., the makespan, is earliest possible. We consider a semi-online variant (introduced for equal speeds) by Azar and Regev, where the jobs are arriving one after the other, while the scheduling algorithm knows the optimum value of the corresponding offline problem. One can ask how close any possible algorithm could get to the optimum value, that is, to give a lower bound on the competitive ratio: the supremum over ratios between the value of the solution given by the algorithm and the optimal offline solution. We contribute to this question by constructing tight lower bounds for all values of
s
in the intervals
[
1
+
21
4
,
3
+
73
8
]
≈
[
1.3956
,
1.443
]
and
[
5
3
,
4
+
133
9
]
≈
[
5
3
,
1.7258
]
, except a very narrow interval.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer Berlin Heidelberg</pub><doi>10.1007/s10100-018-0536-9</doi><tpages>24</tpages><orcidid>https://orcid.org/0000-0003-3637-4066</orcidid><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 1435-246X |
| ispartof | Central European journal of operations research, 2019-12, Vol.27 (4), p.1107-1130 |
| issn | 1435-246X 1613-9178 |
| language | eng |
| recordid | cdi_proquest_journals_2022075271 |
| source | Business Source Ultimate【Trial: -2024/12/31】【Remote access available】; ABI/INFORM Global; Springer Nature |
| subjects | Algorithms Business and Management Lower bounds Machinery Magneto-electric machines Mathematical optimization Methods Operations research Operations Research/Decision Theory Optimization Original Paper Production scheduling Scheduling Scheduling (Management) Scheduling algorithms |
| title | Tight lower bounds for semi-online scheduling on two uniform machines with known optimum |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T12%3A45%3A07IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_proqu&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Tight%20lower%20bounds%20for%20semi-online%20scheduling%20on%20two%20uniform%20machines%20with%20known%20optimum&rft.jtitle=Central%20European%20journal%20of%20operations%20research&rft.au=D%C3%B3sa,%20Gy%C3%B6rgy&rft.date=2019-12-01&rft.volume=27&rft.issue=4&rft.spage=1107&rft.epage=1130&rft.pages=1107-1130&rft.issn=1435-246X&rft.eissn=1613-9178&rft_id=info:doi/10.1007/s10100-018-0536-9&rft_dat=%3Cgale_proqu%3EA706498816%3C/gale_proqu%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c500t-6e4063738d590877f1cd45adce0deb9812d5488a185cec5e626aaa650a4fee1c3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2022075271&rft_id=info:pmid/&rft_galeid=A706498816&rfr_iscdi=true |