Constraint based local search for flowshops with sequence-dependent setup times

摘要

Permutation flowshop scheduling problem with sequence-dependent setup times (PFSP-SDST) and makespan minimisation is NP-hard. It has important practical applications, for example, in the cider industry and the print industry. There exist several metaheuristic algorithms to solve this problem. However, within practical time limits, those algorithms still either find low quality solutions or struggle with large problems. In this paper, we have proposed a simple but effective local search algorithm, called constraint based local search (CBLS) algorithm, which transforms the SDST constraints into an auxiliary objective function and uses the auxiliary objective function to guide the search towards the optimal value of the actual objective function. Our motivation comes from the constraint optimisation models in artificial intelligence (AI), where constraint-based informed decisions are of particular interest instead of random-based decisions. Our experimental results on well-known 480 instances of PFSP-SDST show that the proposed CBLS algorithm outperforms existing state-of-the-art PFSP-SDST algorithms. Moreover, our algorithm obtains new upper bounds for 204 out of 360 medium-and large-sized problem instances.