Scheduling with multi-attribute setup times on two identical parallel machines

This paper considers a real-life identical parallel scheduling problem originating from the manufacturing plant producing polyvinyl chloride leather products. In the considered scheduling problem, each job has some attributes and each attribute has several different levels. Because there is at least one different level of attribute between two adjacent jobs, it is necessary to make a setup adjustment whenever there is a switch from processing a job to a different job on each machine. The problem can be classified as a scheduling problem to minimize the makespan on two identical parallel machines with multi-attribute setup times. A constructive heuristic, named COIT, is first proposed for the problem and evaluated by comparing with the current scheduling method used by the case plant. To further improve the solution, a variable neighborhood search (VNS) metaheuristic is presented and compared with a mixed integer programming model. The computational results show that the COIT heuristic outperforms the current scheduling method with a significant improvement, and the VNS can further improve the solution.