Multi-Objective Parallel Machine Scheduling with Eligibility Constraints for the Kitting of Metal Structural Parts

Abstract

This paper studied a class of coupling problems of material assignment, part nesting, kit delivery and parallel machine scheduling. The aim of this paper was to solve the scheduling problem of metal structural part processing and welding assembly with eligibility constraints. A two-stage mixed-integer programming model was constructed. The eligibility constraints took into account the material type of parts and nesting. The objectives were to minimize the makespan, maximize material utilization and minimize the kit delivery metrics (kitting time and numbers of earliness and tardiness of kits). A hierarchical optimization approach was proposed. The scheduling model was solved by using the Gurobi solver in the first stage, and the results were used to constrain the second stage. The second stage of the scheduling model was solved using an improved multi-objective genetic algorithm. Due to the strong coupling relationships among the sorting of parts, the sorting of each profile and the sorting of each material, a hybrid encoding and decoding mode was designed for part sorting with eligibility constraints. Finally, the proposed scheduling approach was applied to actual production cases. The data showed that when the number of components exceeded 300 (the number of parts was about 1500), the material utilization reached 95%. Choosing a suitable number of machines, machine utilization reached 90%. The results demonstrated the effectiveness of the proposed scheduling model and algorithm.

Keywords

• eligibility constraints
• metal structural part
• kitting
• parallel machine scheduling
• multi-objective optimization