A blocking flow shop deteriorating scheduling problem via a hybrid chemical reaction optimization

Introduction

Flow shop scheduling is one of the most well-known and difficult combination optimization problems,^1,2 and it has a widespread application in manufacturing systems, even in service systems.^3,4 In recent years, it has gained an increasing concern from operational and industrial communities.^5,6 As for the computational complexity, it has been proved that the flow shop scheduling problem with more than two machines is nondeterministic polynomial (NP)-hard in the strong sense.⁷ Therefore, the flow shop scheduling problem has been extensively studied in the past few years.^8–11

In order to make the scheduling models more suitable for real-world manufacturing systems, Gupta and Gupta¹² investigated a deteriorating scheduling model in a single machine case, where the processing time of jobs was an increasing function of their starting time. Since the deteriorating scheduling model can describe a scheduling problem more comprehensively, it has attracted much attention in manufacturing and service systems. The flow shop deteriorating scheduling problem has been extensively studied in recent years,^13–16 and it has been proven to be an NP-hard problem when there are more than two machines.¹⁷ The blocking flow shop scheduling problem is one of the best known branches of the flow shop scheduling problem.^18,19 It usually appears in the environment where the processed jobs are kept in the machines because of lack of intermediate storage²⁰ or storage is not allowed in the manufacturing process due to the technological requirements.²¹ In the blocking flow shop scheduling problem, there are no buffers between machines, and the jobs that have been completed processing on a machine has to remain on that machine until the next machine is available. Since the blocking flow shop scheduling problem is important in both academic and engineering applications, great attention has been paid to develop its effective techniques.^22–25 However, the blocking flow shop deteriorating scheduling problem has not attracted so much attention in existing studies. Over the past decades, some efforts have been made to the two-machine flow shop deteriorating scheduling problem.^26–28 Nevertheless, the existing scheduling model and solution techniques are not suitable for solving the blocking flow shop deteriorating scheduling problem when there are more than two machines in a blocking flow shop environment. Therefore, it...