IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i13p2305-d853900.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Yung-Chia Chang & Kuei-Hu Chang & Ching-Ping Zheng, 2022. "Application of a Non-Dominated Sorting Genetic Algorithm to Solve a Bi-Objective Scheduling Problem Regarding Printed Circuit Boards," Mathematics, MDPI, vol. 10(13), pages 1-21, July.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:13:p:2305-:d:853900
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/13/2305/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/13/2305/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Robert McNaughton, 1959. "Scheduling with Deadlines and Loss Functions," Management Science, INFORMS, vol. 6(1), pages 1-12, October.
    2. Xu, Rui & Chen, Huaping & Li, Xueping, 2013. "A bi-objective scheduling problem on batch machines via a Pareto-based ant colony system," International Journal of Production Economics, Elsevier, vol. 145(1), pages 371-386.
    3. Ching-Jong Liao & Cheng-Hsiung Lee & Hsing-Tzu Tsai, 2016. "Scheduling with multi-attribute set-up times on unrelated parallel machines," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4839-4853, August.
    4. Vallada, Eva & Ruiz, Rubén, 2011. "A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 211(3), pages 612-622, June.
    5. Yenisey, Mehmet Mutlu & Yagmahan, Betul, 2014. "Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends," Omega, Elsevier, vol. 45(C), pages 119-135.
    6. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    7. Song, Yanli & Chen, Xin & Zhou, Jialong & Du, Tao & Xie, Feng & Guo, Haifeng, 2022. "Research on performance of passive heat supply tower based on the back propagation neural network," Energy, Elsevier, vol. 250(C).
    8. Abouei Ardakan, Mostafa & Rezvan, Mohammad Taghi, 2018. "Multi-objective optimization of reliability–redundancy allocation problem with cold-standby strategy using NSGA-II," Reliability Engineering and System Safety, Elsevier, vol. 172(C), pages 225-238.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Chun-Lung Chen, 2023. "An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints," Mathematics, MDPI, vol. 11(6), pages 1-14, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zeynep Adak & Mahmure Övül Arıoğlu Akan & Serol Bulkan, 0. "Multiprocessor open shop problem: literature review and future directions," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-23.
    2. Zeynep Adak & Mahmure Övül Arıoğlu Akan & Serol Bulkan, 2020. "Multiprocessor open shop problem: literature review and future directions," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 547-569, August.
    3. Victor Fernandez-Viagas & Luis Sanchez-Mediano & Alvaro Angulo-Cortes & David Gomez-Medina & Jose Manuel Molina-Pariente, 2022. "The Permutation Flow Shop Scheduling Problem with Human Resources: MILP Models, Decoding Procedures, NEH-Based Heuristics, and an Iterated Greedy Algorithm," Mathematics, MDPI, vol. 10(19), pages 1-32, September.
    4. Chen, Wenchong & Gong, Xuejian & Rahman, Humyun Fuad & Liu, Hongwei & Qi, Ershi, 2021. "Real-time order acceptance and scheduling for data-enabled permutation flow shops: Bilevel interactive optimization with nonlinear integer programming," Omega, Elsevier, vol. 105(C).
    5. Ana Rita Antunes & Marina A. Matos & Ana Maria A. C. Rocha & Lino A. Costa & Leonilde R. Varela, 2022. "A Statistical Comparison of Metaheuristics for Unrelated Parallel Machine Scheduling Problems with Setup Times," Mathematics, MDPI, vol. 10(14), pages 1-19, July.
    6. Liu Guiqing & Li Kai & Cheng Bayi, 2015. "Preemptive Scheduling with Controllable Processing Times on Parallel Machines," Journal of Systems Science and Information, De Gruyter, vol. 3(1), pages 68-76, February.
    7. Dung-Ying Lin & Tzu-Yun Huang, 2021. "A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem," Mathematics, MDPI, vol. 9(7), pages 1-20, April.
    8. Zaretalab, Arash & Sharifi, Mani & Guilani, Pedram Pourkarim & Taghipour, Sharareh & Niaki, Seyed Taghi Akhavan, 2022. "A multi-objective model for optimizing the redundancy allocation, component supplier selection, and reliable activities for multi-state systems," Reliability Engineering and System Safety, Elsevier, vol. 222(C).
    9. Hoogeveen, J. A. & Lenstra, J. K. & Veltman, B., 1996. "Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard," European Journal of Operational Research, Elsevier, vol. 89(1), pages 172-175, February.
    10. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    11. Scholl, Armin & Becker, Christian, 2006. "State-of-the-art exact and heuristic solution procedures for simple assembly line balancing," European Journal of Operational Research, Elsevier, vol. 168(3), pages 666-693, February.
    12. Weiwei Cui & Biao Lu, 2020. "A Bi-Objective Approach to Minimize Makespan and Energy Consumption in Flow Shops with Peak Demand Constraint," Sustainability, MDPI, vol. 12(10), pages 1-22, May.
    13. Liang Tang & Zhihong Jin & Xuwei Qin & Ke Jing, 2019. "Supply chain scheduling in a collaborative manufacturing mode: model construction and algorithm design," Annals of Operations Research, Springer, vol. 275(2), pages 685-714, April.
    14. Mellal, Mohamed Arezki & Zio, Enrico, 2020. "System reliability-redundancy optimization with cold-standby strategy by an enhanced nest cuckoo optimization algorithm," Reliability Engineering and System Safety, Elsevier, vol. 201(C).
    15. Leah Epstein, 2023. "Parallel solutions for preemptive makespan scheduling on two identical machines," Journal of Scheduling, Springer, vol. 26(1), pages 61-76, February.
    16. Han, Bin & Zhang, Wenjun & Lu, Xiwen & Lin, Yingzi, 2015. "On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: Minimizing the makespan and delivery cost," European Journal of Operational Research, Elsevier, vol. 244(3), pages 704-714.
    17. Jin Xu & Natarajan Gautam, 2020. "On competitive analysis for polling systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(6), pages 404-419, September.
    18. Chen, Lin & Ye, Deshi & Zhang, Guochuan, 2018. "Parallel machine scheduling with speed-up resources," European Journal of Operational Research, Elsevier, vol. 268(1), pages 101-112.
    19. Jun-Ho Lee & Hyun-Jung Kim, 2021. "A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence-dependent setup times, and limited setup operators," Flexible Services and Manufacturing Journal, Springer, vol. 33(4), pages 992-1026, December.
    20. Li, Shuai & Chi, Xuefen & Yu, Baozhu, 2022. "An improved particle swarm optimization algorithm for the reliability–redundancy allocation problem with global reliability," Reliability Engineering and System Safety, Elsevier, vol. 225(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:13:p:2305-:d:853900. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.