The BrowneYechiali single-machine sequence is optimal for flow-shops
An optimal polynomial time solution for minimum makespan on a single machine with linear job deterioration is known in the scheduling literature for about 20 years (Browne and Yechiali, 1990 [1]). An extension of this result to flow-shop settings has not been published since then. In this note we provide this result: we show that the BrowneYechiali sequence remains optimal for flow-shops, i.e. we present a polynomial time ( O ( n log n ) ) solution for minimum makespan on an m-machine flow-shop with linear job deterioration.
flow-shop makespan scheduling linear deterioration