Identical parallel machine scheduling with time-dependent processing times
Résumé
This paper introduces an exact algorithm which minimizes the total completion time for a two parallel machine problem with time dependent deterioration effect (2|rj=t0,pj=bj×tj|Cmax). By deterioration effect, we mean that the processing time of a job is defined by an increasing function of its starting time. The proposed algorithm combines a lexicographic search and a list scheduling rule based on a largest deteriorating rate first strategy to provide the optimal solution.This algorithm is extended to solve the general version of this problem (P|rj=t0, pj=bj×tj|Cmax). This extension is obtained by transforming the original m-machine problem into a series of two-machine sub-problems, and solving them repeatedly using the optimal algorithm cited above.A numerical experiment study is performed to evaluate the effectiveness of the proposed algorithm by comparison with three heuristic methods inspired by the literature. The obtained results show that for the two-machine case, the proposed optimal algorithm performs very well even for large instances. For the general case with m >2, the obtained results show that the extended version of the algorithm outperforms significantly the heuristic methods.