Loading…

Non-clairvoyant scheduling for weighted flow time

A non-clairvoyant scheduler makes decisions having no knowledge of jobs. It does not know when the jobs will arrive in the future, that is, it is online, and how long the jobs will be executed after they arrive. For non-clairvoyant scheduling, we first study the problem to minimize the total stretch...

Full description

Saved in:

Bibliographic Details
Published in:	Information processing letters 2003-07, Vol.87 (1), p.31-37
Main Authors:	Kim, Jae-Hoon, Chwa, Kyung-Yong
Format:	Article
Language:	English
Subjects:	Algorithms Applied sciences Computer science control theory systems Computer systems performance. Reliability Decision making ESP Exact sciences and technology Extrasensory perception Flow control Flow time Non-clairvoyance Operational research and scientific management Operational research. Management science Production scheduling Scheduling Scheduling, sequencing Software Studies
Citations:	Items that this one cites
Online Access:	Get full text
Tags:	Add Tag No Tags, Be the first to tag this record!

cited_by
cites	cdi_FETCH-LOGICAL-c312t-6033c4a0e90c9a50c2bd57ae146bb4cf04251b5c1b4c617f8c861df51db5f61d3
container_end_page	37
container_issue	1
container_start_page	31
container_title	Information processing letters
container_volume	87
creator	Kim, Jae-Hoon Chwa, Kyung-Yong
description	A non-clairvoyant scheduler makes decisions having no knowledge of jobs. It does not know when the jobs will arrive in the future, that is, it is online, and how long the jobs will be executed after they arrive. For non-clairvoyant scheduling, we first study the problem to minimize the total stretch. And we also consider the case in which the weights of jobs are known when they arrive, while their lengths are still unknown. In this case, we find a schedule to minimize the total weighted flow time. The weighted versions of well-known algorithms, Round Robin and Balance, are investigated.
doi_str_mv	10.1016/S0020-0190(03)00231-X
format	article
fullrecord	<record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_237285999</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S002001900300231X</els_id><sourcerecordid>345865601</sourcerecordid><originalsourceid>FETCH-LOGICAL-c312t-6033c4a0e90c9a50c2bd57ae146bb4cf04251b5c1b4c617f8c861df51db5f61d3</originalsourceid><addsrcrecordid>eNqFUF1LwzAUDaLgnP4EoQiCPlTvbZq0eRIZfsHQBxX2FtI02SK1nUm3sX9vtok--nTvgfPBOYScIlwhIL9-BcggBRRwAfQyAorpZI8MsCyylCOKfTL4pRySoxA-AIDntBgQfO7aVDfK-WW3Vm2fBD0z9aJx7TSxnU9Wxk1nvakT23SrpHef5pgcWNUEc_Jzh-T9_u5t9JiOXx6eRrfjVFPM-pQDpTpXYARooRjorKpZoQzmvKpybSHPGFZMYwQcC1vqkmNtGdYVs_GjQ3K285377mthQi8_uoVvY6TMaJGVTAgRSWxH0r4LwRsr5959Kr-WCHIzjtyOIzfNJVC5HUdOou78x1wFrRrrVatd-BPnhSh5rDAkNzueiU2XzngZtDOtNrXzRvey7tw_Sd8fZne6</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>237285999</pqid></control><display><type>article</type><title>Non-clairvoyant scheduling for weighted flow time</title><source>ScienceDirect Freedom Collection 2022-2024</source><source>ScienceDirect Journals</source><source>Backfile Package - Mathematics (Legacy) [YMT]</source><creator>Kim, Jae-Hoon ; Chwa, Kyung-Yong</creator><creatorcontrib>Kim, Jae-Hoon ; Chwa, Kyung-Yong</creatorcontrib><description>A non-clairvoyant scheduler makes decisions having no knowledge of jobs. It does not know when the jobs will arrive in the future, that is, it is online, and how long the jobs will be executed after they arrive. For non-clairvoyant scheduling, we first study the problem to minimize the total stretch. And we also consider the case in which the weights of jobs are known when they arrive, while their lengths are still unknown. In this case, we find a schedule to minimize the total weighted flow time. The weighted versions of well-known algorithms, Round Robin and Balance, are investigated.</description><identifier>ISSN: 0020-0190</identifier><identifier>EISSN: 1872-6119</identifier><identifier>DOI: 10.1016/S0020-0190(03)00231-X</identifier><identifier>CODEN: IFPLAT</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Algorithms ; Applied sciences ; Computer science; control theory; systems ; Computer systems performance. Reliability ; Decision making ; ESP ; Exact sciences and technology ; Extrasensory perception ; Flow control ; Flow time ; Non-clairvoyance ; Operational research and scientific management ; Operational research. Management science ; Production scheduling ; Scheduling ; Scheduling, sequencing ; Software ; Studies</subject><ispartof>Information processing letters, 2003-07, Vol.87 (1), p.31-37</ispartof><rights>2003</rights><rights>2003 INIST-CNRS</rights><rights>Copyright Elsevier Sequoia S.A. Jul 16, 2003</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c312t-6033c4a0e90c9a50c2bd57ae146bb4cf04251b5c1b4c617f8c861df51db5f61d3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.sciencedirect.com/science/article/pii/S002001900300231X$$EHTML$$P50$$Gelsevier$$H</linktohtml><link.rule.ids>314,776,780,3415,3550,27903,27904,45951,45981</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=14798660$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Kim, Jae-Hoon</creatorcontrib><creatorcontrib>Chwa, Kyung-Yong</creatorcontrib><title>Non-clairvoyant scheduling for weighted flow time</title><title>Information processing letters</title><description>A non-clairvoyant scheduler makes decisions having no knowledge of jobs. It does not know when the jobs will arrive in the future, that is, it is online, and how long the jobs will be executed after they arrive. For non-clairvoyant scheduling, we first study the problem to minimize the total stretch. And we also consider the case in which the weights of jobs are known when they arrive, while their lengths are still unknown. In this case, we find a schedule to minimize the total weighted flow time. The weighted versions of well-known algorithms, Round Robin and Balance, are investigated.</description><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Computer science; control theory; systems</subject><subject>Computer systems performance. Reliability</subject><subject>Decision making</subject><subject>ESP</subject><subject>Exact sciences and technology</subject><subject>Extrasensory perception</subject><subject>Flow control</subject><subject>Flow time</subject><subject>Non-clairvoyance</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><subject>Production scheduling</subject><subject>Scheduling</subject><subject>Scheduling, sequencing</subject><subject>Software</subject><subject>Studies</subject><issn>0020-0190</issn><issn>1872-6119</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2003</creationdate><recordtype>article</recordtype><recordid>eNqFUF1LwzAUDaLgnP4EoQiCPlTvbZq0eRIZfsHQBxX2FtI02SK1nUm3sX9vtok--nTvgfPBOYScIlwhIL9-BcggBRRwAfQyAorpZI8MsCyylCOKfTL4pRySoxA-AIDntBgQfO7aVDfK-WW3Vm2fBD0z9aJx7TSxnU9Wxk1nvakT23SrpHef5pgcWNUEc_Jzh-T9_u5t9JiOXx6eRrfjVFPM-pQDpTpXYARooRjorKpZoQzmvKpybSHPGFZMYwQcC1vqkmNtGdYVs_GjQ3K285377mthQi8_uoVvY6TMaJGVTAgRSWxH0r4LwRsr5959Kr-WCHIzjtyOIzfNJVC5HUdOou78x1wFrRrrVatd-BPnhSh5rDAkNzueiU2XzngZtDOtNrXzRvey7tw_Sd8fZne6</recordid><startdate>20030716</startdate><enddate>20030716</enddate><creator>Kim, Jae-Hoon</creator><creator>Chwa, Kyung-Yong</creator><general>Elsevier B.V</general><general>Elsevier Science</general><general>Elsevier Sequoia S.A</general><scope>IQODW</scope><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>20030716</creationdate><title>Non-clairvoyant scheduling for weighted flow time</title><author>Kim, Jae-Hoon ; Chwa, Kyung-Yong</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c312t-6033c4a0e90c9a50c2bd57ae146bb4cf04251b5c1b4c617f8c861df51db5f61d3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2003</creationdate><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Computer science; control theory; systems</topic><topic>Computer systems performance. Reliability</topic><topic>Decision making</topic><topic>ESP</topic><topic>Exact sciences and technology</topic><topic>Extrasensory perception</topic><topic>Flow control</topic><topic>Flow time</topic><topic>Non-clairvoyance</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><topic>Production scheduling</topic><topic>Scheduling</topic><topic>Scheduling, sequencing</topic><topic>Software</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Kim, Jae-Hoon</creatorcontrib><creatorcontrib>Chwa, Kyung-Yong</creatorcontrib><collection>Pascal-Francis</collection><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>Information processing letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Kim, Jae-Hoon</au><au>Chwa, Kyung-Yong</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Non-clairvoyant scheduling for weighted flow time</atitle><jtitle>Information processing letters</jtitle><date>2003-07-16</date><risdate>2003</risdate><volume>87</volume><issue>1</issue><spage>31</spage><epage>37</epage><pages>31-37</pages><issn>0020-0190</issn><eissn>1872-6119</eissn><coden>IFPLAT</coden><abstract>A non-clairvoyant scheduler makes decisions having no knowledge of jobs. It does not know when the jobs will arrive in the future, that is, it is online, and how long the jobs will be executed after they arrive. For non-clairvoyant scheduling, we first study the problem to minimize the total stretch. And we also consider the case in which the weights of jobs are known when they arrive, while their lengths are still unknown. In this case, we find a schedule to minimize the total weighted flow time. The weighted versions of well-known algorithms, Round Robin and Balance, are investigated.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/S0020-0190(03)00231-X</doi><tpages>7</tpages></addata></record>
fulltext	fulltext
identifier	ISSN: 0020-0190
ispartof	Information processing letters, 2003-07, Vol.87 (1), p.31-37
issn	0020-0190 1872-6119
language	eng
recordid	cdi_proquest_journals_237285999
source	ScienceDirect Freedom Collection 2022-2024; ScienceDirect Journals; Backfile Package - Mathematics (Legacy) [YMT]
subjects	Algorithms Applied sciences Computer science control theory systems Computer systems performance. Reliability Decision making ESP Exact sciences and technology Extrasensory perception Flow control Flow time Non-clairvoyance Operational research and scientific management Operational research. Management science Production scheduling Scheduling Scheduling, sequencing Software Studies
title	Non-clairvoyant scheduling for weighted flow time
url	http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-24T23%3A08%3A00IST&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=Non-clairvoyant%20scheduling%20for%20weighted%20flow%20time&rft.jtitle=Information%20processing%20letters&rft.au=Kim,%20Jae-Hoon&rft.date=2003-07-16&rft.volume=87&rft.issue=1&rft.spage=31&rft.epage=37&rft.pages=31-37&rft.issn=0020-0190&rft.eissn=1872-6119&rft.coden=IFPLAT&rft_id=info:doi/10.1016/S0020-0190(03)00231-X&rft_dat=%3Cproquest_cross%3E345865601%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c312t-6033c4a0e90c9a50c2bd57ae146bb4cf04251b5c1b4c617f8c861df51db5f61d3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=237285999&rft_id=info:pmid/&rfr_iscdi=true