Online nonpreemptive scheduling of equal-length jobs on two identical machines

We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P 2 | p j = p , r j...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on algorithms 2008-11, Vol.5 (1), p.1-18
Main Authors: Goldwasser, Michael H., Pedigo, Mark
Format: Article
Language:English
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-c272t-f575b0e71fc4ac3c5d30383a824017992b359a59bd68f2bf4c0a460243aab8f13
cites cdi_FETCH-LOGICAL-c272t-f575b0e71fc4ac3c5d30383a824017992b359a59bd68f2bf4c0a460243aab8f13
container_end_page 18
container_issue 1
container_start_page 1
container_title ACM transactions on algorithms
container_volume 5
creator Goldwasser, Michael H.
Pedigo, Mark
description We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P 2 | p j = p , r j | Σ Ū j . The problem is known to be polynomially solvable in an offline setting. In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.
doi_str_mv 10.1145/1435375.1435377
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_34638500</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>34638500</sourcerecordid><originalsourceid>FETCH-LOGICAL-c272t-f575b0e71fc4ac3c5d30383a824017992b359a59bd68f2bf4c0a460243aab8f13</originalsourceid><addsrcrecordid>eNo9kD1PwzAYhC0EEqUws3piS2v7teNkRBVfUkUXmCPHed2mcuw0TkD8e4paMT0n3emkO0LuOVtwLtWSS1Cg1eJEfUFmXMkyywHg8l8LdU1uUtozBiVAMSPvm-DbgDTE0A-IXT-2X0iT3WEzHY0tjY7iYTI-8xi2447uY51oDHT8jrRtMIytNZ52xu6ONemWXDnjE96dOSefz08fq9dsvXl5Wz2uMyu0GDOntKoZau6sNBasaoBBAaYQknFdlqIGVRpV1k1eOFE7aZmRORMSjKkLx2FOHk69_RAPE6ax6tpk0XsTME6pAplDoY4r52R5CtohpjSgq_qh7czwU3FW_f1WnX87U8MvcA9gPQ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>34638500</pqid></control><display><type>article</type><title>Online nonpreemptive scheduling of equal-length jobs on two identical machines</title><source>Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list)</source><creator>Goldwasser, Michael H. ; Pedigo, Mark</creator><creatorcontrib>Goldwasser, Michael H. ; Pedigo, Mark</creatorcontrib><description>We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P 2 | p j = p , r j | Σ Ū j . The problem is known to be polynomially solvable in an offline setting. In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.</description><identifier>ISSN: 1549-6325</identifier><identifier>EISSN: 1549-6333</identifier><identifier>DOI: 10.1145/1435375.1435377</identifier><language>eng</language><ispartof>ACM transactions on algorithms, 2008-11, Vol.5 (1), p.1-18</ispartof><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c272t-f575b0e71fc4ac3c5d30383a824017992b359a59bd68f2bf4c0a460243aab8f13</citedby><cites>FETCH-LOGICAL-c272t-f575b0e71fc4ac3c5d30383a824017992b359a59bd68f2bf4c0a460243aab8f13</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Goldwasser, Michael H.</creatorcontrib><creatorcontrib>Pedigo, Mark</creatorcontrib><title>Online nonpreemptive scheduling of equal-length jobs on two identical machines</title><title>ACM transactions on algorithms</title><description>We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P 2 | p j = p , r j | Σ Ū j . The problem is known to be polynomially solvable in an offline setting. In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.</description><issn>1549-6325</issn><issn>1549-6333</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2008</creationdate><recordtype>article</recordtype><recordid>eNo9kD1PwzAYhC0EEqUws3piS2v7teNkRBVfUkUXmCPHed2mcuw0TkD8e4paMT0n3emkO0LuOVtwLtWSS1Cg1eJEfUFmXMkyywHg8l8LdU1uUtozBiVAMSPvm-DbgDTE0A-IXT-2X0iT3WEzHY0tjY7iYTI-8xi2447uY51oDHT8jrRtMIytNZ52xu6ONemWXDnjE96dOSefz08fq9dsvXl5Wz2uMyu0GDOntKoZau6sNBasaoBBAaYQknFdlqIGVRpV1k1eOFE7aZmRORMSjKkLx2FOHk69_RAPE6ax6tpk0XsTME6pAplDoY4r52R5CtohpjSgq_qh7czwU3FW_f1WnX87U8MvcA9gPQ</recordid><startdate>200811</startdate><enddate>200811</enddate><creator>Goldwasser, Michael H.</creator><creator>Pedigo, Mark</creator><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>200811</creationdate><title>Online nonpreemptive scheduling of equal-length jobs on two identical machines</title><author>Goldwasser, Michael H. ; Pedigo, Mark</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c272t-f575b0e71fc4ac3c5d30383a824017992b359a59bd68f2bf4c0a460243aab8f13</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2008</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Goldwasser, Michael H.</creatorcontrib><creatorcontrib>Pedigo, Mark</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science 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><jtitle>ACM transactions on algorithms</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Goldwasser, Michael H.</au><au>Pedigo, Mark</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Online nonpreemptive scheduling of equal-length jobs on two identical machines</atitle><jtitle>ACM transactions on algorithms</jtitle><date>2008-11</date><risdate>2008</risdate><volume>5</volume><issue>1</issue><spage>1</spage><epage>18</epage><pages>1-18</pages><issn>1549-6325</issn><eissn>1549-6333</eissn><abstract>We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P 2 | p j = p , r j | Σ Ū j . The problem is known to be polynomially solvable in an offline setting. In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.</abstract><doi>10.1145/1435375.1435377</doi><tpages>18</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1549-6325
ispartof ACM transactions on algorithms, 2008-11, Vol.5 (1), p.1-18
issn 1549-6325
1549-6333
language eng
recordid cdi_proquest_miscellaneous_34638500
source Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list)
title Online nonpreemptive scheduling of equal-length jobs on two identical machines
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T08%3A19%3A05IST&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=Online%20nonpreemptive%20scheduling%20of%20equal-length%20jobs%20on%20two%20identical%20machines&rft.jtitle=ACM%20transactions%20on%20algorithms&rft.au=Goldwasser,%20Michael%20H.&rft.date=2008-11&rft.volume=5&rft.issue=1&rft.spage=1&rft.epage=18&rft.pages=1-18&rft.issn=1549-6325&rft.eissn=1549-6333&rft_id=info:doi/10.1145/1435375.1435377&rft_dat=%3Cproquest_cross%3E34638500%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c272t-f575b0e71fc4ac3c5d30383a824017992b359a59bd68f2bf4c0a460243aab8f13%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=34638500&rft_id=info:pmid/&rfr_iscdi=true