Openshop and flowshop scheduling to minimize sum of completion times (Q1086145)

This paper deals with efficiently solvable special cases of open shop and permutation-flowshop scheduling where the objective function is minimum sum of completion times. Two O(mn) algorithms for open shop scheduling where all operations have equal processing times, are presented. The first constructs a no-wait schedule and the second a schedule where both criteria (sum of completion times and schedule length) take on their minimal values. For permutation-flowshop scheduling where processing times satisfy dominancy and/or ordered relations, SPT rules are proved to be optimal.