A Heuristic Procedure for Parallel Sequencing with Choice of Machines

An algorithm is described for parallel sequencing on two machines of a set of operations with partial ordering constraints. Some assignments are fixed and some are flexible allowing a choice of machines; operation times for the flexible assignments are assumed to be equal. The algorithm establishes a parallel sequence that seeks to minimize the elapsed time required for both machines to complete processing without testing the set of possible permutations on operations. Assignment decision rules are formulated to balance the parallel sequences considering accumulated time and remaining future commitments on each machine. Experimental results comparing programmed solutions with lower bounds of running time are given.