TY - JOUR
T1 - Application of a Non-Dominated Sorting Genetic Algorithm to Solve a Bi-Objective Scheduling Problem regarding Printed Circuit Boards
AU - Chang, Yung Chia
AU - Chang, Kuei Hu
AU - Zheng, Ching Ping
N1 - Publisher Copyright:
© 2022 by the authors. Licensee MDPI, Basel, Switzerland.
PY - 2022/7/1
Y1 - 2022/7/1
N2 - An unrelated parallel machine scheduling problem motivated by the scheduling of a printed circuit board assembly (PCBA) under surface mount technology (SMT) is discussed in this paper. This problem involved machine eligibility restrictions, sequence-dependent setup times, precedence constraints, unequal job release times, and constraints of shared resources with the objectives of minimizing the makespan and the total job tardiness. Since this scheduling problem is NP-hard, a mathematical model was first built to describe the problem, and a heuristic approach using a non-dominated sorting genetic algorithm (NSGA-II) was then designed to solve this biobjective problem. Multiple near-optimal solutions were provided using the Pareto front solution and crowding distance concepts. To demonstrate the efficiency and effectiveness of the proposed approach, this study first tested the proposed approach by solving test problems on a smaller scale. It was found that the proposed approach could obtain optimal solutions for small test problems. A real set of work orders and production data was provided by a famous hardware manufacturer in Taiwan. The solutions suggested by the proposed approach were provided using Gantt charts to visually assist production planners to make decisions. It was found that the proposed approach could not only successfully improve the planning time but also provide several feasible schedules with equivalent performance for production planners to choose from.
AB - An unrelated parallel machine scheduling problem motivated by the scheduling of a printed circuit board assembly (PCBA) under surface mount technology (SMT) is discussed in this paper. This problem involved machine eligibility restrictions, sequence-dependent setup times, precedence constraints, unequal job release times, and constraints of shared resources with the objectives of minimizing the makespan and the total job tardiness. Since this scheduling problem is NP-hard, a mathematical model was first built to describe the problem, and a heuristic approach using a non-dominated sorting genetic algorithm (NSGA-II) was then designed to solve this biobjective problem. Multiple near-optimal solutions were provided using the Pareto front solution and crowding distance concepts. To demonstrate the efficiency and effectiveness of the proposed approach, this study first tested the proposed approach by solving test problems on a smaller scale. It was found that the proposed approach could obtain optimal solutions for small test problems. A real set of work orders and production data was provided by a famous hardware manufacturer in Taiwan. The solutions suggested by the proposed approach were provided using Gantt charts to visually assist production planners to make decisions. It was found that the proposed approach could not only successfully improve the planning time but also provide several feasible schedules with equivalent performance for production planners to choose from.
KW - machine eligibility restrictions
KW - multi-objective
KW - non-dominated sorting genetic algorithm II
KW - resource constraints
KW - unrelated parallel machine scheduling problem
UR - http://www.scopus.com/inward/record.url?scp=85133571351&partnerID=8YFLogxK
U2 - 10.3390/math10132305
DO - 10.3390/math10132305
M3 - Article
AN - SCOPUS:85133571351
SN - 2227-7390
VL - 10
JO - Mathematics
JF - Mathematics
IS - 13
M1 - 2305
ER -