Nonstrict Vector Summation in Multi-Operation Scheduling

摘要

The authors consider several multi-operation scheduling problems with m machinesand n jobs, including flow shop, open shop, assembly line, and a few special cases of job shop with the makespan criterion. It is demonstrated that the problems in question can be efficiently solved by approximation algorithms with fairly good performance guaranteed in worst case. The algorithms constructed are based on a geometric technique called 'nonstrict vector summation'. It consists of asigning an (m-1)-dimensional vector to each job and then finding an order in which the resulting vectors should be summed so that all partial sums lied within half-spaces of the best possible family (with respect to a certain objective function). The partial sums are allowed sometimes go out of this or that half-space of the family.