Total Completion Time in a Two-machine Flowshop with Deteriorating Tasks

This paper deals with two-machine flowshop problems with deteriorating tasks, i.e. tasks whose processing times are a nondecreasing function that depend on the length of the waiting periods. We consider the so-called Restricted Problem. This problem can be defined as follows: for a given permutation of tasks, find an optimal placement on two machines so that the total completion time is minimized. We will show that the Restricted Problem is nontrivial. We give some properties for the optimal placement and we propose an optimal placement algorithm.