TITLE

Nonstrict vector summation in multi-operation scheduling

AUTHOR(S)
Sevastianov, Sergey
PUB. DATE
November 1998
SOURCE
Annals of Operations Research;1998, Vol. 83 Issue 1-4, p179
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
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 - l)-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 lo 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 lmax (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 lmax as large as at least 7 times the maximum processing time of an operation, we can find the optimal schedule in O(n log n) time.
ACCESSION #
18669666

 

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics