A Note on Permutation Flow Shop Problem

In this paper we present two approximation algorithms for the permutation flow shop problem with makespan objective. The first algorithm has an absolute performance guarantee, the second one is an O(square root of m log m)-approximation algorithm. The last result is almost best possible approximatio...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2004-07, Vol.129 (1-4), p.247-252
Main Author: Sviridenko, M.I.
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Codes
Job shops
Operations research
Random variables
Schedules
Studies
Citations: 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-c288t-6c0962f1f5b57e950a74067760451db54e66586c82ba06c33afabe7eaf86376a3
cites
container_end_page 252
container_issue 1-4
container_start_page 247
container_title Annals of operations research
container_volume 129
creator Sviridenko, M.I.
description In this paper we present two approximation algorithms for the permutation flow shop problem with makespan objective. The first algorithm has an absolute performance guarantee, the second one is an O(square root of m log m)-approximation algorithm. The last result is almost best possible approximation algorithm which can be obtained using the trivial lower bound (maximum of the maximum machine load and the maximum job length)(Potts, Shmoys, and Williamson, 1991). [PUBLICATION ABSTRACT]
doi_str_mv 10.1023/B:ANOR.0000030691.65576.28
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_214507959</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>727243531</sourcerecordid><originalsourceid>FETCH-LOGICAL-c288t-6c0962f1f5b57e950a74067760451db54e66586c82ba06c33afabe7eaf86376a3</originalsourceid><addsrcrecordid>eNpFkE1Lw0AURQdRMFb_Q-jGVeKbmbw3k-7aYlUobfFjPUziBFuSTp2kiP_exAq-zX2Lw71wGBtzSDkIeTebTFfr5xSGk0A5TwlRUSr0GYs4KpHkUupzFoHALEEp4ZJdte2uxznXGLHbabzynYv9Pt640Bw72237f1H7r_jlwx_iTfBF7ZprdlHZunU3fzlib4v71_ljslw_PM2ny6QUWncJlZCTqHiFBSqXI1iVASlFkCF_LzBzRKip1KKwQKWUtrKFU85WmqQiK0dsfOo9BP95dG1ndv4Y9v2kETxDUDnmPTQ5QWXwbRtcZQ5h29jwbTiYwYuZmcGL-fdifr0YoeUPLMtUSw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>214507959</pqid></control><display><type>article</type><title>A Note on Permutation Flow Shop Problem</title><source>Business Source Ultimate【Trial: -2024/12/31】【Remote access available】</source><source>ABI/INFORM Global (ProQuest)</source><source>Springer Nature</source><creator>Sviridenko, M.I.</creator><creatorcontrib>Sviridenko, M.I.</creatorcontrib><description>In this paper we present two approximation algorithms for the permutation flow shop problem with makespan objective. The first algorithm has an absolute performance guarantee, the second one is an O(square root of m log m)-approximation algorithm. The last result is almost best possible approximation algorithm which can be obtained using the trivial lower bound (maximum of the maximum machine load and the maximum job length)(Potts, Shmoys, and Williamson, 1991). [PUBLICATION ABSTRACT]</description><identifier>ISSN: 0254-5330</identifier><identifier>EISSN: 1572-9338</identifier><identifier>DOI: 10.1023/B:ANOR.0000030691.65576.28</identifier><language>eng</language><publisher>New York: Springer Nature B.V</publisher><subject>Algorithms ; Approximation ; Codes ; Job shops ; Operations research ; Random variables ; Schedules ; Studies</subject><ispartof>Annals of operations research, 2004-07, Vol.129 (1-4), p.247-252</ispartof><rights>Copyright (c) 2004 Kluwer Academic Publishers</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c288t-6c0962f1f5b57e950a74067760451db54e66586c82ba06c33afabe7eaf86376a3</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/214507959/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/214507959?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>Sviridenko, M.I.</creatorcontrib><title>A Note on Permutation Flow Shop Problem</title><title>Annals of operations research</title><description>In this paper we present two approximation algorithms for the permutation flow shop problem with makespan objective. The first algorithm has an absolute performance guarantee, the second one is an O(square root of m log m)-approximation algorithm. The last result is almost best possible approximation algorithm which can be obtained using the trivial lower bound (maximum of the maximum machine load and the maximum job length)(Potts, Shmoys, and Williamson, 1991). [PUBLICATION ABSTRACT]</description><subject>Algorithms</subject><subject>Approximation</subject><subject>Codes</subject><subject>Job shops</subject><subject>Operations research</subject><subject>Random variables</subject><subject>Schedules</subject><subject>Studies</subject><issn>0254-5330</issn><issn>1572-9338</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2004</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNpFkE1Lw0AURQdRMFb_Q-jGVeKbmbw3k-7aYlUobfFjPUziBFuSTp2kiP_exAq-zX2Lw71wGBtzSDkIeTebTFfr5xSGk0A5TwlRUSr0GYs4KpHkUupzFoHALEEp4ZJdte2uxznXGLHbabzynYv9Pt640Bw72237f1H7r_jlwx_iTfBF7ZprdlHZunU3fzlib4v71_ljslw_PM2ny6QUWncJlZCTqHiFBSqXI1iVASlFkCF_LzBzRKip1KKwQKWUtrKFU85WmqQiK0dsfOo9BP95dG1ndv4Y9v2kETxDUDnmPTQ5QWXwbRtcZQ5h29jwbTiYwYuZmcGL-fdifr0YoeUPLMtUSw</recordid><startdate>20040701</startdate><enddate>20040701</enddate><creator>Sviridenko, M.I.</creator><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7TA</scope><scope>7TB</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</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>HCIFZ</scope><scope>JG9</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>KR7</scope><scope>L.-</scope><scope>L6V</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</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></search><sort><creationdate>20040701</creationdate><title>A Note on Permutation Flow Shop Problem</title><author>Sviridenko, M.I.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c288t-6c0962f1f5b57e950a74067760451db54e66586c82ba06c33afabe7eaf86376a3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2004</creationdate><topic>Algorithms</topic><topic>Approximation</topic><topic>Codes</topic><topic>Job shops</topic><topic>Operations research</topic><topic>Random variables</topic><topic>Schedules</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Sviridenko, M.I.</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Materials Business File</collection><collection>Mechanical &amp; 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 Collection</collection><collection>Science Database (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 &amp; Engineering Collection</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>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Engineering Research Database</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>Materials Research Database</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>ABI/INFORM Global (ProQuest)</collection><collection>Computing Database</collection><collection>Science Database</collection><collection>Engineering Database</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; 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>Annals of operations research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Sviridenko, M.I.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A Note on Permutation Flow Shop Problem</atitle><jtitle>Annals of operations research</jtitle><date>2004-07-01</date><risdate>2004</risdate><volume>129</volume><issue>1-4</issue><spage>247</spage><epage>252</epage><pages>247-252</pages><issn>0254-5330</issn><eissn>1572-9338</eissn><abstract>In this paper we present two approximation algorithms for the permutation flow shop problem with makespan objective. The first algorithm has an absolute performance guarantee, the second one is an O(square root of m log m)-approximation algorithm. The last result is almost best possible approximation algorithm which can be obtained using the trivial lower bound (maximum of the maximum machine load and the maximum job length)(Potts, Shmoys, and Williamson, 1991). [PUBLICATION ABSTRACT]</abstract><cop>New York</cop><pub>Springer Nature B.V</pub><doi>10.1023/B:ANOR.0000030691.65576.28</doi><tpages>6</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0254-5330
ispartof Annals of operations research, 2004-07, Vol.129 (1-4), p.247-252
issn 0254-5330
1572-9338
language eng
recordid cdi_proquest_journals_214507959
source Business Source Ultimate【Trial: -2024/12/31】【Remote access available】; ABI/INFORM Global (ProQuest); Springer Nature
subjects Algorithms
Approximation
Codes
Job shops
Operations research
Random variables
Schedules
Studies
title A Note on Permutation Flow Shop Problem
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T11%3A51%3A30IST&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=A%20Note%20on%20Permutation%20Flow%20Shop%20Problem&rft.jtitle=Annals%20of%20operations%20research&rft.au=Sviridenko,%20M.I.&rft.date=2004-07-01&rft.volume=129&rft.issue=1-4&rft.spage=247&rft.epage=252&rft.pages=247-252&rft.issn=0254-5330&rft.eissn=1572-9338&rft_id=info:doi/10.1023/B:ANOR.0000030691.65576.28&rft_dat=%3Cproquest_cross%3E727243531%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c288t-6c0962f1f5b57e950a74067760451db54e66586c82ba06c33afabe7eaf86376a3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=214507959&rft_id=info:pmid/&rfr_iscdi=true