File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1080/07408170600941623
- Scopus: eid_2-s2.0-33847765320
- WOS: WOS:000245029700009
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Probabilistic asymptotic analysis of stochastic online scheduling problems
Title | Probabilistic asymptotic analysis of stochastic online scheduling problems |
---|---|
Authors | |
Keywords | On-line scheduling Asymptotic performance ratio Stochastic Release time Total weighted completion time |
Issue Date | 2007 |
Citation | IIE Transactions (Institute of Industrial Engineers), 2007, v. 39, n. 5, p. 525-538 How to Cite? |
Abstract | In the stochastic online scheduling environment, jobs with unknown release times and weights arrive over time. Upon arrival, the information on the weight of the job is revealed but the processing requirement remains unknown until the job is finished. In this paper we consider the objective of minimizing the total weighted completion time. With the assumptions that job weights are bounded, machine capacity is adequate, and processing requirements are bounded and identical and independently distributed across the machines and jobs, we show that any nondelay algorithm is asymptotically optimal for the stochastic online single machine problem, flow shop problem, and uniform parallel machine problem. Our simulation studies of these stochastic online scheduling problems show that two generic nondelay algorithms perform very well as long as the number of jobs is larger than 100. |
Persistent Identifier | http://hdl.handle.net/10722/295991 |
ISSN | 2018 Impact Factor: 2.884 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chen, Gang | - |
dc.contributor.author | Shen, Zuo Jun Max | - |
dc.date.accessioned | 2021-02-11T04:52:36Z | - |
dc.date.available | 2021-02-11T04:52:36Z | - |
dc.date.issued | 2007 | - |
dc.identifier.citation | IIE Transactions (Institute of Industrial Engineers), 2007, v. 39, n. 5, p. 525-538 | - |
dc.identifier.issn | 0740-817X | - |
dc.identifier.uri | http://hdl.handle.net/10722/295991 | - |
dc.description.abstract | In the stochastic online scheduling environment, jobs with unknown release times and weights arrive over time. Upon arrival, the information on the weight of the job is revealed but the processing requirement remains unknown until the job is finished. In this paper we consider the objective of minimizing the total weighted completion time. With the assumptions that job weights are bounded, machine capacity is adequate, and processing requirements are bounded and identical and independently distributed across the machines and jobs, we show that any nondelay algorithm is asymptotically optimal for the stochastic online single machine problem, flow shop problem, and uniform parallel machine problem. Our simulation studies of these stochastic online scheduling problems show that two generic nondelay algorithms perform very well as long as the number of jobs is larger than 100. | - |
dc.language | eng | - |
dc.relation.ispartof | IIE Transactions (Institute of Industrial Engineers) | - |
dc.subject | On-line scheduling | - |
dc.subject | Asymptotic performance ratio | - |
dc.subject | Stochastic | - |
dc.subject | Release time | - |
dc.subject | Total weighted completion time | - |
dc.title | Probabilistic asymptotic analysis of stochastic online scheduling problems | - |
dc.type | Article | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1080/07408170600941623 | - |
dc.identifier.scopus | eid_2-s2.0-33847765320 | - |
dc.identifier.volume | 39 | - |
dc.identifier.issue | 5 | - |
dc.identifier.spage | 525 | - |
dc.identifier.epage | 538 | - |
dc.identifier.eissn | 1545-8830 | - |
dc.identifier.isi | WOS:000245029700009 | - |
dc.identifier.issnl | 0740-817X | - |