IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v55y2004i11d10.1057_palgrave.jors.2601795.html
   My bibliography  Save this article

Algorithms for the wafer probing scheduling problem with sequence-dependent set-up time and due date restrictions

Author

Listed:
  • W L Pearn

    (National Chiao Tung University)

  • S H Chung

    (National Chiao Tung University)

  • M H Yang

    (National United University)

  • Y H Chen

    (National Chiao Tung University)

Abstract

In this paper, we consider the wafer probing scheduling problem (WPSP) to sequence families of jobs on identical parallel machines with due date restrictions. The machine set-up time is sequentially dependent on the product types of the jobs processed on the machine. The objective is to minimize the total machine workload without violating the machine capacity and job due date restrictions. The WPSP is a variation of the classical parallel-machine scheduling problem, that can be transformed into the vehicle-routing problem with time windows (VRPTW). One can therefore solve the WPSP efficiently using existing VRPTW algorithms. We apply four existing savings algorithms presented in the literature including sequential, parallel, generalized, and matching based savings, and develop three modifications called the modified sequential, the compound matching based, and the modified compound matching-based savings algorithms, to solve the WPSP. Based on the characteristics of the wafer probing process, a set of test problems is generated for testing purposes. Computational results show that the three proposed modified algorithms perform remarkably well.

Suggested Citation

  • W L Pearn & S H Chung & M H Yang & Y H Chen, 2004. "Algorithms for the wafer probing scheduling problem with sequence-dependent set-up time and due date restrictions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(11), pages 1194-1207, November.
    • Handle: RePEc:pal:jorsoc:v:55:y:2004:i:11:d:10.1057_palgrave.jors.2601795
    DOI: 10.1057/palgrave.jors.2601795
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601795
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2601795?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. Cheng, T. C. E. & Sin, C. C. S., 1990. "A state-of-the-art review of parallel-machine scheduling research," European Journal of Operational Research, Elsevier, vol. 47(3), pages 271-292, August.
    2. Kemal Altinkemer & Bezalel Gavish, 1991. "Parallel Savings Based Heuristics for the Delivery Problem," Operations Research, INFORMS, vol. 39(3), pages 456-469, June.
    3. Dessouky, Maged M. & Dessouky, Mohamed I. & Verma, Sushil K., 1998. "Flowshop scheduling with identical jobs and uniform parallel machines," European Journal of Operational Research, Elsevier, vol. 109(3), pages 620-631, September.
    4. W L Pearn & S H Chung & M H Yang, 2002. "The wafer probing scheduling problem (WPSP)," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(8), pages 864-874, August.
    5. Herrmann, Jeffrey & Proth, Jean-Marie & Sauer, Nathalie, 1997. "Heuristics for unrelated machine scheduling with precedence constraints," European Journal of Operational Research, Elsevier, vol. 102(3), pages 528-537, November.
    6. Lee, Young Hoon & Pinedo, Michael, 1997. "Scheduling jobs on parallel machines with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 100(3), pages 464-474, August.
    7. Schutten, J. M. J. & Leussink, R. A. M., 1996. "Parallel machine scheduling with release dates, due dates and family setup times," International Journal of Production Economics, Elsevier, vol. 46(1), pages 119-125, December.
    8. Ho, Johnny C. & Chang, Yih-Long, 1995. "Minimizing the number of tardy jobs for m parallel machines," European Journal of Operational Research, Elsevier, vol. 84(2), pages 343-355, July.
    9. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    10. Gabrel, Virginie, 1995. "Scheduling jobs within time windows on identical parallel machines: New model and algorithms," European Journal of Operational Research, Elsevier, vol. 83(2), pages 320-329, June.
    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. Hyun Joong Yoon & Junjae Chae, 2019. "Simulation Study for Semiconductor Manufacturing System: Dispatching Policies for a Wafer Test Facility," Sustainability, MDPI, vol. 11(4), pages 1-21, February.
    2. Shih-Wei Lin & Zne-Jung Lee & Kuo-Ching Ying & Rong-Ho Lin, 2011. "Meta-heuristic algorithms for wafer sorting scheduling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 165-174, January.
    3. Allahverdi, Ali & Ng, C.T. & Cheng, T.C.E. & Kovalyov, Mikhail Y., 2008. "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 985-1032, June.
    4. R-H Huang & C-L Yang & H-T Huang, 2010. "Parallel machine scheduling with common due windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(4), pages 640-646, April.

    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. Pearn, W. L. & Chung, S. H. & Chen, A. Y. & Yang, M. H., 2004. "A case study on the multistage IC final testing scheduling problem with reentry," International Journal of Production Economics, Elsevier, vol. 88(3), pages 257-267, April.
    2. Chen, Jeng-Fung & Wu, Tai-Hsi, 2006. "Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints," Omega, Elsevier, vol. 34(1), pages 81-89, January.
    3. 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.
    4. Yao, Yu & Zhu, Xiaoning & Dong, Hongyu & Wu, Shengnan & Wu, Hailong & Carol Tong, Lu & Zhou, Xuesong, 2019. "ADMM-based problem decomposition scheme for vehicle routing problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 129(C), pages 156-174.
    5. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    6. Michele Ciavotta & Carlo Meloni & Marco Pranzo, 2016. "Speeding up a Rollout algorithm for complex parallel machine scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4993-5009, August.
    7. Y Gajpal & P Abad, 2010. "Saving-based algorithms for vehicle routing problem with simultaneous pickup and delivery," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(10), pages 1498-1509, October.
    8. Gouveia, Luis, 1995. "A result on projection for the vehicle routing ptoblem," European Journal of Operational Research, Elsevier, vol. 85(3), pages 610-624, September.
    9. Gilbert Laporte, 2007. "What you should know about the vehicle routing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 811-819, December.
    10. Siwate Rojanasoonthon & Jonathan Bard, 2005. "A GRASP for Parallel Machine Scheduling with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 32-51, February.
    11. Chang, Zhiqi & Ding, Jian-Ya & Song, Shiji, 2019. "Distributionally robust scheduling on parallel machines under moment uncertainty," European Journal of Operational Research, Elsevier, vol. 272(3), pages 832-846.
    12. Jun-Ho Lee & Hoon Jang, 2019. "Uniform Parallel Machine Scheduling with Dedicated Machines, Job Splitting and Setup Resources," Sustainability, MDPI, vol. 11(24), pages 1-23, December.
    13. Merve Cengiz Toklu, 2023. "A fuzzy multi-criteria approach based on Clarke and Wright savings algorithm for vehicle routing problem in humanitarian aid distribution," Journal of Intelligent Manufacturing, Springer, vol. 34(5), pages 2241-2261, June.
    14. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    15. Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
    16. Bornstein, Claudio Thomas & Alcoforado, Luciane Ferreira & Maculan, Nelson, 2005. "A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem," European Journal of Operational Research, Elsevier, vol. 165(3), pages 649-656, September.
    17. Andrew Lim & Brian Rodrigues & Zhou Xu, 2007. "A m‐parallel crane scheduling problem with a non‐crossing constraint," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 115-127, March.
    18. S Rojanasoonthon & J F Bard & S D Reddy, 2003. "Algorithms for parallel machine scheduling: a case study of the tracking and data relay satellite system," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(8), pages 806-821, August.
    19. Jürgen Strohhecker & Michael Hamann & Jörn-Henrik Thun, 2016. "Loading and sequencing heuristics for job scheduling on two unrelated parallel machines with long, sequence-dependent set-up times," International Journal of Production Research, Taylor & Francis Journals, vol. 54(22), pages 6747-6767, November.
    20. Poot, A. & Kant, G. & Wagelmans, A.P.M., 1999. "A savings based method for real-life vehicle routing problems," Econometric Institute Research Papers EI 9938/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.

    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:pal:jorsoc:v:55:y:2004:i:11:d:10.1057_palgrave.jors.2601795. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.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.