A DECOMPOSITION APPROACH FOR THE MACHINE SCHEDULING PROBLEM

Publisher Website
Google Scholar
Abstract
This paper investigates the solution of the machine scheduling problem by a decomposition approach. The original problem is partitioned into a series of smaller, more manageable sub-problems. Considerable experimentation is conducled to study the statistical characteristics of this approach and to compare results with those obtained by complete or partial enumeration. The relative efficiencies of the decomposition solutions are investigated. The hypothesis that the mean of the schedule times shifts toward the minimum as the number of jobs in each sub-problem increases is tested. Finally, the computer times spent to obtain the complete or partial enumeration and decomposition solutions are compared.