Sequencing jobs with random processing times to minimize weighted completion time variance

X. Cai and S. Zhou

Annals of Operations Research, 1997, vol. 70, issue 0, 260 pages

Abstract: We examine the problem of sequencing a set of jobs on a single machine, where each job has a random processing time and is associated with a known, job-dependent weight. The objective is to minimize the expectation of the weighted variance of job completion times. We establish the NP-completeness of this problem, and further show that the problem under some compatible conditions is NP-complete in the ordinary sense. We introduce the concept of a W-shaped solution for the problem and find that an optimal W-shaped sequence exists under the compatible conditions. We propose an exact algorithm, based on this W-shaped property, which can generate an optimal solution in pseudopolynomial time. Copyright Kluwer Academic Publishers 1997

Keywords: Scheduling/sequencing; stochastic programming; variance minimization; NP-completeness; dynamic programming (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018926305578 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:70:y:1997:i:0:p:241-260:10.1023/a:1018926305578

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018926305578

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().