NONSTRICT VECTOR SUMMATION IN MULTI-OPERATION SCHEDULING

We consider several multi-operation scheduling problems with m machine s 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 b y approximation algorithms with fairly good performance guarantee in t he worst case. The algorithms constructed are based on a geometric tec hnique called ''nonstrict vector summation''. It consists of assigning an (m - 1)-dimensional vector to each job and then finding an order i n which these vectors should be summed so that all partial sums would lie within a given family of half-spaces (specified for a given schedu ling problem). The partial sums are allowed sometimes to go out of thi s or that half-space of the family, which explains the term ''nonstric t'' in the title of the paper. For the open shop problem, this techniq ue 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 ca se of three machines and I,,as large as at least 7 times the maximum p rocessing time of an operation, we can find the optimal schedule in O( n log n) time.