Application of a Non-Dominated Sorting Genetic Algorithm to Solve a Bi-Objective Scheduling Problem Regarding Printed Circuit Boards

Yung-Chia Chang, Kuei-Hu Chang and Ching-Ping Zheng
Additional contact information
Yung-Chia Chang: Department of Industrial Engineering and Management, National Yang Ming Chiao Tung University, Hsinchu 300, Taiwan
Kuei-Hu Chang: Department of Management Sciences, R.O.C. Military Academy, Kaohsiung 830, Taiwan
Ching-Ping Zheng: Department of Industrial Engineering and Management, National Yang Ming Chiao Tung University, Hsinchu 300, Taiwan

Mathematics, 2022, vol. 10, issue 13, 1-21

Abstract: 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 bi-objective 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.

Keywords: multi-objective; unrelated parallel machine scheduling problem; non-dominated sorting genetic algorithm II; machine eligibility restrictions; resource constraints (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/13/2305/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/13/2305/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:13:p:2305-:d:853900

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().