IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v278y2024ics0925527324002706.html
   My bibliography  Save this article

Scheduling of memory chips for final testing on parallel machines considering power constraints and deteriorating effects

Author

Listed:
  • Lu, Shaojun
  • Hu, Chiwei
  • Kong, Min
  • Fathollahi-Fard, Amir M.
  • Dulebenets, Maxim A.

Abstract

This paper delves into the intricate scheduling strategies crucial for the final testing phase of memory chip manufacturing within the semiconductor industry and other related sectors. It specifically addresses the complex serial-batching scheduling problem, where memory chips are tested on parallel machines under power constraints and chip deterioration effects. The processing time for each chip is significantly influenced by both the cumulative processing time of preceding chips and the power requirements for testing. We formulate this real-world optimization problem using a mixed integer nonlinear programming model. Exact solutions for small instances are obtained using a commercial solver. However, due to the model's complexity, we also develop heuristic solutions to efficiently handle larger instances. Based on the derivation of structural properties, we develop two tailored heuristic algorithms to determine the schedule for the final testing of memory chips. Additionally, we propose a refined Variable Neighborhood Search algorithm (VNS-H) that seamlessly integrates five local search strategies with two supplementary heuristic algorithms, dynamically alternating between them to ensure a balance between computational efficiency and the quality of the solutions obtained. Additionally, we establish a lower bound to validate the effectiveness of these solutions, particularly for large-scale instances. To validate the efficacy and robustness of our proposed metaheuristic algorithm, we conduct a rigorous comparison of the VNS-H algorithm with five other metaheuristic algorithms that have promising performance in various optimization problems. The results highlight the superior performance of the VNS-H algorithm. In small-scale instances, our VNS-H algorithm achieves an average makespan that is 5.52% lower compared to the original VNS. For large-scale instances, the VNS-H algorithm reduces the average makespan by 13.46% compared to VNS. Finally, we discuss the managerial implications of our findings, providing insights specifically tailored to semiconductor manufacturing enterprises based on the outcomes of this study.

Suggested Citation

  • Lu, Shaojun & Hu, Chiwei & Kong, Min & Fathollahi-Fard, Amir M. & Dulebenets, Maxim A., 2024. "Scheduling of memory chips for final testing on parallel machines considering power constraints and deteriorating effects," International Journal of Production Economics, Elsevier, vol. 278(C).
    • Handle: RePEc:eee:proeco:v:278:y:2024:i:c:s0925527324002706
    DOI: 10.1016/j.ijpe.2024.109413
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527324002706
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2024.109413?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Oğuzhan Ahmet Arık & M. Duran Toksarı, 2018. "Multi-objective fuzzy parallel machine scheduling problems under fuzzy job deterioration and learning effects," International Journal of Production Research, Taylor & Francis Journals, vol. 56(7), pages 2488-2505, April.
    2. Xiaoxia Tian & Jingwen Yan & Yanchun Yang & Chi Xiao & Qi Zhou, 2019. "Parameter identification of a nonlinear model using an improved version of simulated annealing," International Journal of Distributed Sensor Networks, , vol. 15(2), pages 15501477198, February.
    3. Susan Scott & Wanda Orlikowski, 2022. "The Digital Undertow: How the Corollary Effects of Digital Transformation Affect Industry Standards," Information Systems Research, INFORMS, vol. 33(1), pages 311-336, March.
    4. Glock, Christoph H. & Grosse, Eric H., 2021. "The impact of controllable production rates on the performance of inventory systems: A systematic review of the literature," European Journal of Operational Research, Elsevier, vol. 288(3), pages 703-720.
    5. Chin-Chia Wu & Ameni Azzouz & I-Hong Chung & Win-Chin Lin & Lamjed Ben Said, 2019. "A two-stage three-machine assembly scheduling problem with deterioration effect," International Journal of Production Research, Taylor & Francis Journals, vol. 57(21), pages 6634-6647, November.
    6. Sara Ceschia & Rosita Guido & Andrea Schaerf, 2020. "Solving the static INRC-II nurse rostering problem by simulated annealing based on large neighborhoods," Annals of Operations Research, Springer, vol. 288(1), pages 95-113, May.
    7. W-H Kuo & D-L Yang, 2008. "Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(3), pages 416-420, March.
    8. Cheng, T. C. E. & Ding, Q. & Lin, B. M. T., 2004. "A concise survey of scheduling with time-dependent processing times," European Journal of Operational Research, Elsevier, vol. 152(1), pages 1-13, January.
    9. Pei, Jun & Liu, Xinbao & Fan, Wenjuan & Pardalos, Panos M. & Lu, Shaojun, 2019. "A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers," Omega, Elsevier, vol. 82(C), pages 55-69.
    10. Jing-jing Wang & Ling Wang, 2019. "Decoding methods for the flow shop scheduling with peak power consumption constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 57(10), pages 3200-3218, May.
    11. Ye, Shunran & Meng, Yichao & Feng, Shuhai & Liu, Shuo & Zhang, Xinhua, 2024. "A mechanism to overcome barriers to inter-provincial power supply substitution in China," Utilities Policy, Elsevier, vol. 88(C).
    12. Yenny Alexandra Paredes-Astudillo & Valérie Botta-Genoulaz & Jairo R. Montoya-Torres, 2024. "Impact of learning effect modelling in flowshop scheduling with makespan minimisation based on the Nawaz-Enscore-Ham algorithm," International Journal of Production Research, Taylor & Francis Journals, vol. 62(6), pages 1999-2014, March.
    13. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    14. Jun Pei & Qingru Song & Baoyu Liao & Xinbao Liu & Panos M. Pardalos, 2021. "Parallel-machine serial-batching scheduling with release times under the effects of position-dependent learning and time-dependent deterioration," Annals of Operations Research, Springer, vol. 298(1), pages 407-444, March.
    15. Hu, Yusha & Man, Yi, 2022. "Two-stage energy scheduling optimization model for complex industrial process and its industrial verification," Renewable Energy, Elsevier, vol. 193(C), pages 879-894.
    16. Sid Browne & Uri Yechiali, 1990. "Scheduling Deteriorating Jobs on a Single Processor," Operations Research, INFORMS, vol. 38(3), pages 495-498, June.
    17. Jianfa Cao & Jinjiang Yuan & Wenjie Li & Hailin Bu, 2011. "Online scheduling on batching machines to minimise the total weighted completion time of jobs with precedence constraints and identical processing times," International Journal of Systems Science, Taylor & Francis Journals, vol. 42(1), pages 51-55.
    18. Muter, İbrahim, 2020. "Exact algorithms to minimize makespan on single and parallel batch processing machines," European Journal of Operational Research, Elsevier, vol. 285(2), pages 470-483.
    19. Xinyu Sun & Xin-Na Geng, 2019. "Single-machine scheduling with deteriorating effects and machine maintenance," International Journal of Production Research, Taylor & Francis Journals, vol. 57(10), pages 3186-3199, May.
    20. Scott, Susan V. & Orlikowski, Wanda J., 2022. "The digital undertow: how the corollary effects of digital transformation affect industry standards," LSE Research Online Documents on Economics 112426, London School of Economics and Political Science, LSE Library.
    21. Jun Pei & Xinbao Liu & Panos M. Pardalos & Wenjuan Fan & Shanlin Yang, 2017. "Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times," Annals of Operations Research, Springer, vol. 249(1), pages 175-195, February.
    22. Shaowen Lan & Wenjuan Fan & Shanlin Yang & Nenad Mladenović & Panos M. Pardalos, 2022. "Solving a multiple-qualifications physician scheduling problem with multiple types of tasks by dynamic programming and variable neighborhood search," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 73(9), pages 2043-2058, October.
    23. Sandeep Kumar & Bhupesh Kumar Lad, 2017. "Integrated production and maintenance planning for parallel machine system considering cost of rejection," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(7), pages 834-846, July.
    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. Huang, Dawen & Zhou, Dengji, 2025. "Improving the operational reliability of aeroengines based on coupled thermodynamics and dynamics stochastic responses," Reliability Engineering and System Safety, Elsevier, vol. 260(C).

    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. Delorme, Maxence & Iori, Manuel & Mendes, Nilson F.M., 2021. "Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events," European Journal of Operational Research, Elsevier, vol. 295(3), pages 823-837.
    2. Min Kong & Xinbao Liu & Jun Pei & Panos M. Pardalos & Nenad Mladenovic, 2020. "Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines," Journal of Global Optimization, Springer, vol. 78(4), pages 693-715, December.
    3. Jun Pei & Qingru Song & Baoyu Liao & Xinbao Liu & Panos M. Pardalos, 2021. "Parallel-machine serial-batching scheduling with release times under the effects of position-dependent learning and time-dependent deterioration," Annals of Operations Research, Springer, vol. 298(1), pages 407-444, March.
    4. C-C He & C-C Wu & W-C Lee, 2009. "Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1759-1766, December.
    5. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    6. Jun Pei & Xinbao Liu & Panos M. Pardalos & Wenjuan Fan & Shanlin Yang, 2017. "Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times," Annals of Operations Research, Springer, vol. 249(1), pages 175-195, February.
    7. Wang, Ling & Sun, Lin-Yan & Sun, Lin-Hui & Wang, Ji-Bo, 2010. "On three-machine flow shop scheduling with deteriorating jobs," International Journal of Production Economics, Elsevier, vol. 125(1), pages 185-189, May.
    8. Wu, Chin-Chia & Lee, Wen-Chiung, 2006. "Two-machine flowshop scheduling to minimize mean flow time under linear deterioration," International Journal of Production Economics, Elsevier, vol. 103(2), pages 572-584, October.
    9. Xiaoyu Yu & Jingyi Qian & Yajing Zhang & Min Kong, 2023. "Supply Chain Scheduling Method for the Coordination of Agile Production and Port Delivery Operation," Mathematics, MDPI, vol. 11(15), pages 1-24, July.
    10. Jun Pei & Xinbao Liu & Panos M. Pardalos & Athanasios Migdalas & Shanlin Yang, 2017. "Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine," Journal of Global Optimization, Springer, vol. 67(1), pages 251-262, January.
    11. Shaoxiang Zheng & Naiming Xie & Qiao Wu, 2025. "An exact approach for bi-objective non-identical batch processing machines scheduling," Annals of Operations Research, Springer, vol. 346(3), pages 2307-2347, March.
    12. Li, Yongqiang & Li, Gang & Sun, Linyan & Xu, Zhiyong, 2009. "Single machine scheduling of deteriorating jobs to minimize total absolute differences in completion times," International Journal of Production Economics, Elsevier, vol. 118(2), pages 424-429, April.
    13. Abbasali Jafari-Nodoushan & Hassan Khademi Zare & M. M. Lotfi & R. Tavakkoli-Moghaddam, 2021. "Scheduling Piecewise Linear Deteriorating Jobs to Minimize Makespan in a Two-Machine Flowshop," SN Operations Research Forum, Springer, vol. 2(4), pages 1-29, December.
    14. Xinyu Sun & Tao Liu & Xin-Na Geng & Yang Hu & Jing-Xiao Xu, 2023. "Optimization of scheduling problems with deterioration effects and an optional maintenance activity," Journal of Scheduling, Springer, vol. 26(3), pages 251-266, June.
    15. Zhao, Chuan-Li & Tang, Heng-Yong, 2010. "Scheduling deteriorating jobs under disruption," International Journal of Production Economics, Elsevier, vol. 125(2), pages 294-299, June.
    16. Jun Pei & Jinling Wei & Baoyu Liao & Xinbao Liu & Panos M. Pardalos, 2020. "Two-agent scheduling on bounded parallel-batching machines with an aging effect of job-position-dependent," Annals of Operations Research, Springer, vol. 294(1), pages 191-223, November.
    17. C. Ng & Q. Ding & T. Cheng & S. Lam, 2012. "Preemptive repayment policy for multiple loans," Annals of Operations Research, Springer, vol. 192(1), pages 141-150, January.
    18. Bahram Alidaee & Haibo Wang & R. Bryan Kethley & Frank Landram, 2019. "A unified view of parallel machine scheduling with interdependent processing rates," Journal of Scheduling, Springer, vol. 22(5), pages 499-515, October.
    19. Matan Atsmony & Baruch Mor & Gur Mosheiov, 2024. "Single machine scheduling with step-learning," Journal of Scheduling, Springer, vol. 27(3), pages 227-237, June.
    20. Yang, Suh-Jenq & Yang, Dar-Li, 2010. "Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities," Omega, Elsevier, vol. 38(6), pages 528-533, December.

    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:eee:proeco:v:278:y:2024:i:c:s0925527324002706. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    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.