Two-machine flow shop scheduling with deteriorating jobs: minimizing the weighted sum of makespan and total completion time

Abstract

This paper considers a two-machine flow shop scheduling problem with deteriorating jobs in which the processing times of jobs are dependent on their starting times in the sequence. The objective is to minimize the weighted sum of makespan and total completion time. To analyse the problem, we propose a mixed integer programming model, and discuss several polynomially solvable special cases. We also present a branch-and-bound algorithm with several dominance rules, an upper bound and a lower bound. Finally, we present results of computational experiments conducted to evaluate the performance of the proposed model and the exact algorithm.

Keywords:

• scheduling
• flow shop
• bi-criteria
• deteriorating jobs
• branch-and-bound
• heuristics

Acknowledgements

The authors are grateful to the anonymous referees who provided valuable comments and suggestions, which helped us significantly to improve the quality of the paper. The research is supported partly by the Ministry of education of Humanities and Social Science project in China (No. 11YJCZH019), Humanities and Social Science Research Base of Major Projects of Guangdong Province Universities (Nos. 11jdxm63001 and 08jdxm63004), supported by NSFC under 1271060, GDNSF under S2012010009278 and Higher Education Research Fund Projects of GDUT (No.2013WT05).