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

Mixed-Integer Linear Programming Model and Heuristic for Short-Term Scheduling of Pressing Process in Multi-Layer Printed Circuit Board Manufacturing

Author

Listed:
  • Teeradech Laisupannawong

    (Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, Bangkok 10330, Thailand)

  • Boonyarit Intiyot

    (Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, Bangkok 10330, Thailand)

  • Chawalit Jeenanunta

    (School of Management Technology, Sirindhorn International Institute of Technology (SIIT), Thammasat University, Pathum Thani 12120, Thailand)

Abstract

The main stages of printed circuit board (PCB) manufacturing are the design, fabrication, assembly, and testing. This paper focuses on the scheduling of the pressing process, which is a part of the fabrication process of a multi-layer PCB and is a new application since it has never been investigated in the literature. A novel mixed-integer linear programming (MILP) formulation for short-term scheduling of the pressing process is presented. The objective function is to minimize the makespan of the overall process. Moreover, a three-phase-PCB-pressing heuristic (3P-PCB-PH) for short-term scheduling of the pressing process is also presented. To illustrate the proposed MILP model and 3P-PCB-PH, the test problems generated from the real data acquired from a PCB company are solved. The results show that the proposed MILP model can find an optimal schedule for all small- and medium-sized problems but can do so only for some large-sized problems using the CPLEX solver within a time limit of 2 h. However, the proposed 3P-PCB-PH could find an optimal schedule for all problems that the MILP could find using much less computational time. Furthermore, it can also quickly find a near-optimal schedule for other large-sized problems that the MILP could not solved optimally.

Suggested Citation

  • Teeradech Laisupannawong & Boonyarit Intiyot & Chawalit Jeenanunta, 2021. "Mixed-Integer Linear Programming Model and Heuristic for Short-Term Scheduling of Pressing Process in Multi-Layer Printed Circuit Board Manufacturing," Mathematics, MDPI, vol. 9(6), pages 1-25, March.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:6:p:653-:d:519775
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/6/653/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/6/653/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Furini, Fabio & Malaguti, Enrico & Medina Durán, Rosa & Persiani, Alfredo & Toth, Paolo, 2012. "A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size," European Journal of Operational Research, Elsevier, vol. 218(1), pages 251-260.
    2. M Mrad & I Meftahi & M Haouari, 2013. "A branch-and-price algorithm for the two-stage guillotine cutting stock problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(5), pages 629-637, May.
    3. Ji, P. & Sze, M. T. & Lee, W. B., 2001. "A genetic algorithm of determining cycle time for printed circuit board assembly lines," European Journal of Operational Research, Elsevier, vol. 128(1), pages 175-184, January.
    4. Supphakorn Sumetthapiwat & Boonyarit Intiyot & Chawalit Jeenanunta, 2020. "A column generation on two-dimensional cutting stock problem with fixed-size usable leftover and multiple stock sizes," International Journal of Logistics Systems and Management, Inderscience Enterprises Ltd, vol. 35(2), pages 273-288.
    5. Li, Xinyu & Gao, Liang, 2016. "An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 174(C), pages 93-110.
    6. P. C. Gilmore & R. E. Gomory, 1965. "Multistage Cutting Stock Problems of Two and More Dimensions," Operations Research, INFORMS, vol. 13(1), pages 94-120, February.
    Full references (including those not matched with items on IDEAS)

    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. Hadj Salem, Khadija & Silva, Elsa & Oliveira, José Fernando & Carravilla, Maria Antónia, 2023. "Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry," European Journal of Operational Research, Elsevier, vol. 306(2), pages 549-566.
    2. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    3. Jianyu Long & Zhong Zheng & Xiaoqiang Gao & Panos M. Pardalos & Wanzhe Hu, 2020. "An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem," Annals of Operations Research, Springer, vol. 289(2), pages 291-311, June.
    4. Douglas Nogueira Nascimento & Adriana Cristina Cherri & José Fernando Oliveira, 2022. "The two-dimensional cutting stock problem with usable leftovers: mathematical modelling and heuristic approaches," Operational Research, Springer, vol. 22(5), pages 5363-5403, November.
    5. Jean-François Côté & Manuel Iori, 2018. "The Meet-in-the-Middle Principle for Cutting and Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 646-661, November.
    6. Malaguti, Enrico & Medina Durán, Rosa & Toth, Paolo, 2014. "Approaches to real world two-dimensional cutting problems," Omega, Elsevier, vol. 47(C), pages 99-115.
    7. François Clautiaux & Ruslan Sadykov & François Vanderbeck & Quentin Viaud, 2019. "Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 265-297, September.
    8. Rapine, Christophe & Pedroso, Joao Pedro & Akbalik, Ayse, 2022. "The two-dimensional knapsack problem with splittable items in stacks," Omega, Elsevier, vol. 112(C).
    9. Amanda O. C. Ayres & Betania S. C. Campello & Washington A. Oliveira & Carla T. L. S. Ghidini, 2021. "A Bi-Integrated Model for coupling lot-sizing and cutting-stock problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 1047-1076, December.
    10. 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.
    11. Parreño, F. & Alvarez-Valdes, R., 2021. "Mathematical models for a cutting problem in the glass manufacturing industry," Omega, Elsevier, vol. 103(C).
    12. Lunardi, Willian T. & Birgin, Ernesto G. & Ronconi, Débora P. & Voos, Holger, 2021. "Metaheuristics for the online printing shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 293(2), pages 419-441.
    13. Gregory S. Taylor & Yupo Chan & Ghulam Rasool, 2017. "A three-dimensional bin-packing model: exact multicriteria solution and computational complexity," Annals of Operations Research, Springer, vol. 251(1), pages 397-427, April.
    14. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    15. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    16. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R & M. Calle, 2020. "Scheduling a dual-resource flexible job shop with makespan and due date-related criteria," Annals of Operations Research, Springer, vol. 291(1), pages 5-35, August.
    17. W. D. D. Madhavee & N. Saldin & U. C. Vaidyarathna & C. J. Jayawardene, 2018. "A Practical Application of the Generalized Cutting Stock Algorithm," Academic Journal of Applied Mathematical Sciences, Academic Research Publishing Group, vol. 4(3), pages 15-21, 03-2018.
    18. Mhand Hifi & Rym M'Hallah, 2005. "An Exact Algorithm for Constrained Two-Dimensional Two-Staged Cutting Problems," Operations Research, INFORMS, vol. 53(1), pages 140-150, February.
    19. Suliman, S.M.A., 2006. "A sequential heuristic procedure for the two-dimensional cutting-stock problem," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 177-185, February.
    20. M Hifi & M Michrafy, 2006. "A reactive local search-based algorithm for the disjunctively constrained knapsack problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(6), pages 718-726, June.

    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:9:y:2021:i:6:p:653-:d:519775. 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.