Nonstrict vector summationin multi-operation scheduling

Sergey Sevastianov

Annals of Operations Research, 1998, vol. 83, issue 0, 179-212

Abstract: We consider several multi-operation scheduling problems with m machines and n jobs, including flow shop, open shop, assembly line, and a few special cases of job shop with the minimum makespan criterion. It is demonstrated that the problems in question can be efficiently solved by approximation algorithms with fairly good performance guarantee in the worst case. The algorithms constructed are based on a geometric technique called “nonstrict vector summation“. It consists of assigning an (m−1)-dimensional vector to each job and then finding an order in which these vectors should be summed so that all partial sums would lie within a given family of half-spaces (specified for a given scheduling problem).The partial sums are allowed sometimes to go out of this or that half-space of the family, which explains the term “nonstrict” in the title of the paper. For the open shop problem, this technique guarantees its polynomial-time solution, provided that the maximum machine load l max (i.e., the maximum over all machines of the total processing time of operations of a machine) is large enough. In the case of three machines and l max as large as at least 7 times the maximum processing time of an operation, we can find the optimal schedule in O(nlog n) time. Copyright Kluwer Academic Publishers 1998

Date: 1998
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018908013582 (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:83:y:1998:i:0:p:179-212:10.1023/a:1018908013582

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

DOI: 10.1023/A:1018908013582

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 ().