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.

Automated summary

The PFSP-SDST problem with sequence-dependent setup times is NP-hard and has practical applications in industries such as cider and print. The proposed CBLS algorithm transforms constraints into an auxiliary objective function to guide the search towards the optimal value of the actual objective function. Experimental results show that the CBLS algorithm outperforms existing state-of-the-art algorithms and obtains new upper bounds for a significant number of problem instances.