IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v235y2015i1p709-73910.1007-s10479-015-1976-4.html
   My bibliography  Save this article

Grouping genetic algorithms for solving single machine multiple orders per job scheduling problems

Author

Listed:
  • Oleh Sobeyko
  • Lars Mönch

Abstract

In this paper, we discuss scheduling problems motivated by a real-world production setting found in 300-mm semiconductor wafer fabrication facilities (wafer fabs). Front opening unified pods (FOUPs) transfer wafers in 300-mm wafer fabs. Several orders can be grouped in one FOUP. We study lot and single item processing environments. The total weighted tardiness (TWT) and the weighted number of tardy orders (WNTO) objectives are considered. Mixed integer programming (MIP) formulations are presented for the scheduling problems. We prove that the researched scheduling problems are NP-hard. Grouping genetic algorithms (GGAs) are proposed to form the content of the FOUPs. We compare the performance of the GGAs with another GA from the literature available for the problem with TWT measure based on randomly generated problem instances. It turns out that the GGA outperforms the heuristic from the literature for both environments. For the WTNO measure, we assess the performance of the GGA approach using MIP formulations for small-size problem instances and a GA-based heuristic for large-size problem instances. Again, the GGA performs well with respect to solution quality and amount of computing time. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • Oleh Sobeyko & Lars Mönch, 2015. "Grouping genetic algorithms for solving single machine multiple orders per job scheduling problems," Annals of Operations Research, Springer, vol. 235(1), pages 709-739, December.
    • Handle: RePEc:spr:annopr:v:235:y:2015:i:1:p:709-739:10.1007/s10479-015-1976-4
    DOI: 10.1007/s10479-015-1976-4
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-015-1976-4
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-015-1976-4?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. Fehmi Tanrisever & Erhan Kutanoglu, 2008. "Forming and scheduling jobs with capacitated containers in semiconductor manufacturing: Single machine problem," Annals of Operations Research, Springer, vol. 159(1), pages 5-24, March.
    2. Jagadish Jampani & Scott Mason, 2008. "Column generation heuristics for multiple machine, multiple orders per job scheduling problems," Annals of Operations Research, Springer, vol. 159(1), pages 261-273, March.
    3. Laub, Jeffrey D. & Fowler, John W. & Keha, Ahmet B., 2007. "Minimizing makespan with multiple-orders-per-job in a two-machine flowshop," European Journal of Operational Research, Elsevier, vol. 182(1), pages 63-79, October.
    4. Vishnu Erramilli & Scott Mason, 2008. "Multiple orders per job batch scheduling with incompatible jobs," Annals of Operations Research, Springer, vol. 159(1), pages 245-260, March.
    5. Koksalan Kondakci, Suna & Bekiroglu, Tuncay, 1997. "Scheduling with bicriteria: total flowtime and number of tardy jobs," International Journal of Production Economics, Elsevier, vol. 53(1), pages 91-99, November.
    6. Mason, Scott J. & Chen, Jen-Shiang, 2010. "Scheduling multiple orders per job in a single machine to minimize total completion time," European Journal of Operational Research, Elsevier, vol. 207(1), pages 70-77, November.
    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. Jianxin Fang & Brenda Cheang & Andrew Lim, 2023. "Problems and Solution Methods of Machine Scheduling in Semiconductor Manufacturing Operations: A Survey," Sustainability, MDPI, vol. 15(17), pages 1-44, August.
    2. Zdeněk Hanzálek & Přemysl Šůcha, 2017. "Time symmetry of resource constrained project scheduling with general temporal constraints and take-give resources," Annals of Operations Research, Springer, vol. 248(1), pages 209-237, January.
    3. Chen-Fu Chien & Chung-Jen Kuo & Chih-Min Yu, 2020. "Tool allocation to smooth work-in-process for cycle time reduction and an empirical study," Annals of Operations Research, Springer, vol. 290(1), pages 1009-1033, July.
    4. Jens Rocholl & Lars Mönch & John Fowler, 2020. "Bi-criteria parallel batch machine scheduling to minimize total weighted tardiness and electricity cost," Journal of Business Economics, Springer, vol. 90(9), pages 1345-1381, November.

    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. Mason, Scott J. & Chen, Jen-Shiang, 2010. "Scheduling multiple orders per job in a single machine to minimize total completion time," European Journal of Operational Research, Elsevier, vol. 207(1), pages 70-77, November.
    2. Framinan, Jose M. & Perez-Gonzalez, Paz & Fernandez-Viagas, Victor, 2019. "Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures," European Journal of Operational Research, Elsevier, vol. 273(2), pages 401-417.
    3. Jianxin Fang & Brenda Cheang & Andrew Lim, 2023. "Problems and Solution Methods of Machine Scheduling in Semiconductor Manufacturing Operations: A Survey," Sustainability, MDPI, vol. 15(17), pages 1-44, August.
    4. Murat Güngör, 2016. "A note on efficient sequences with respect to total flow time and number of tardy jobs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(4), pages 346-348, June.
    5. Artur Alves Pessoa & Teobaldo Bulhões & Vitor Nesello & Anand Subramanian, 2022. "Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1512-1530, May.
    6. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Research on permutation flow shop scheduling problems with general position-dependent learning effects," Annals of Operations Research, Springer, vol. 211(1), pages 473-480, December.
    7. Erenay, Fatih Safa & Sabuncuoglu, Ihsan & Toptal, Aysegül & Tiwari, Manoj Kumar, 2010. "New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs," European Journal of Operational Research, Elsevier, vol. 201(1), pages 89-98, February.
    8. Eduardo Queiroga & Rian G. S. Pinheiro & Quentin Christ & Anand Subramanian & Artur A. Pessoa, 2021. "Iterated local search for single machine total weighted tardiness batch scheduling," Journal of Heuristics, Springer, vol. 27(3), pages 353-438, June.
    9. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Some results of the worst-case analysis for flow shop scheduling with a learning effect," Annals of Operations Research, Springer, vol. 211(1), pages 481-490, December.
    10. Haral, Uday & Chen, Rew-Win & Ferrell, William Jr & Kurz, Mary Beth, 2007. "Multiobjective single machine scheduling with nontraditional requirements," International Journal of Production Economics, Elsevier, vol. 106(2), pages 574-584, April.
    11. Chen, Rubing & Yuan, Jinjiang & Ng, C.T. & Cheng, T.C.E., 2021. "Single-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterion," European Journal of Operational Research, Elsevier, vol. 293(1), pages 79-92.

    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:spr:annopr:v:235:y:2015:i:1:p:709-739:10.1007/s10479-015-1976-4. 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.springer.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.