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

摘要: Abstract 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 print industry. There exist several metaheuristic algorithms to solve this problem. However, within time limits, those still either find low quality solutions or struggle large problems. In paper, we have proposed a simple but effective local search algorithm, called constraint based (CBLS) which transforms SDST constraints into an auxiliary objective function uses guide towards optimal value of actual function. Our motivation comes from optimisation models artificial intelligence (AI), where constraint-based informed decisions are particular interest instead random-based decisions. experimental results on well-known 480 instances PFSP-SDST show that CBLS algorithm outperforms existing state-of-the-art algorithms. Moreover, our obtains new upper bounds 204 out 360 medium- large-sized instances.