A VARIANT OF THE PERMUTATION FLOW-SHOP MODEL WITH VARIABLE PROCESSINGTIMES

We consider a modification of the classical flow shop problem with inf inite buffer capacities. The processing times on various machines are variable: the more one delays the beginning of an operation, the longe r is its processing time. There are many industrial applications for t his model, for instance in the planning of machine maintenance or serv ice and in steel production where the material will cool during the wa iting periods and has to be reheated for the subsequent process. The p roblem turns out to be already NP-hard in the strong sense for two pro cessors, and in general the optimal schedule is not a permutation sche dule. In the literature, a restricted problem is considered where one wants to determine the optimal release times for the jobs, once their order is given. We shall solve this m-machine flow shop problem by a g reedy placement algorithm. For the two-machine case, where also the op timal order of the jobs has to be determined, several approximate solu tion methods are analysed.