IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v204y2013i1p189-22210.1007-s10479-012-1271-6.html
   My bibliography  Save this article

Makespan minimization in online scheduling with machine eligibility

Author

Listed:
  • Kangbok Lee
  • Joseph Leung
  • Michael Pinedo

Abstract

In this paper we provide a survey of online scheduling in parallel machine environments with machine eligibility constraints and the makespan as objective function. We first give a brief overview of the different parallel machine environments and then survey the various types of machine eligibility constraints, including tree-hierarchical processing sets, Grade of Service processing sets, interval processing sets, and nested processing sets. We furthermore describe the relationships between the various different types of processing sets. We proceed with describing two basic online scheduling paradigms, namely online over list and online over time. For each one of the two paradigms we survey all the results that have been recorded in the literature with regard to each type of machine eligibility constraints. We obtain also several extensions in various directions. In the concluding section we describe the most important open problems in this particular area. Copyright Springer Science+Business Media New York 2013

Suggested Citation

  • Kangbok Lee & Joseph Leung & Michael Pinedo, 2013. "Makespan minimization in online scheduling with machine eligibility," Annals of Operations Research, Springer, vol. 204(1), pages 189-222, April.
    • Handle: RePEc:spr:annopr:v:204:y:2013:i:1:p:189-222:10.1007/s10479-012-1271-6
    DOI: 10.1007/s10479-012-1271-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-012-1271-6
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-012-1271-6?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. Zhiyi Tan & An Zhang, 2010. "A note on hierarchical scheduling on two uniform machines," Journal of Combinatorial Optimization, Springer, vol. 20(1), pages 85-95, July.
    2. Robert McNaughton, 1959. "Scheduling with Deadlines and Loss Functions," Management Science, INFORMS, vol. 6(1), pages 1-12, October.
    3. Leung, Joseph Y.-T. & Li, Chung-Lun, 2008. "Scheduling with processing set restrictions: A survey," International Journal of Production Economics, Elsevier, vol. 116(2), pages 251-262, December.
    4. Jinwen Ou & Joseph Y.‐T. Leung & Chung‐Lun Li, 2008. "Scheduling parallel machines with inclusive processing set restrictions," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(4), pages 328-338, June.
    5. Ming Liu & Chengbin Chu & Yinfeng Xu & Feifeng Zheng, 2011. "Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times," Journal of Combinatorial Optimization, Springer, vol. 21(1), pages 138-149, January.
    6. Leslie A. Hall & Andreas S. Schulz & David B. Shmoys & Joel Wein, 1997. "Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 22(3), pages 513-544, August.
    7. Yiwei Jiang, 2008. "Online scheduling on parallel machines with two GoS levels," Journal of Combinatorial Optimization, Springer, vol. 16(1), pages 28-38, July.
    8. Wu, Yong & Ji, Min & Yang, Qifan, 2012. "Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision," International Journal of Production Economics, Elsevier, vol. 135(1), pages 367-371.
    9. Li-ying Hou & Liying Kang, 2012. "Online scheduling on uniform machines with two hierarchies," Journal of Combinatorial Optimization, Springer, vol. 24(4), pages 593-612, November.
    10. Huo, Yumei & Leung, Joseph Y.-T., 2010. "Parallel machine scheduling with nested processing set restrictions," European Journal of Operational Research, Elsevier, vol. 204(2), pages 229-236, July.
    11. Orion Chassid & Leah Epstein, 2008. "The hierarchical model for load balancing on two machines," Journal of Combinatorial Optimization, Springer, vol. 15(4), pages 305-314, May.
    12. Hark-Chin Hwang & Soo Y. Chang & Yushin Hong, 2004. "A Posterior Competitiveness For List Scheduling Algorithm On Machines With Eligibility Constraints," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 21(01), pages 117-125.
    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. Leung, Joseph Y.-T. & Li, Chung-Lun, 2016. "Scheduling with processing set restrictions: A literature update," International Journal of Production Economics, Elsevier, vol. 175(C), pages 1-11.
    2. Sheng-I Chen & Delvinia Su, 2022. "A multi-stage stochastic programming model of lot-sizing and scheduling problems with machine eligibilities and sequence-dependent setups," Annals of Operations Research, Springer, vol. 311(1), pages 35-50, April.
    3. 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.
    4. Xianglai Qi & Jinjiang Yuan, 2019. "Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(01), pages 1-16, February.
    5. Xianglai Qi & Jinjiang Yuan, 2017. "Semi-online hierarchical scheduling for $$l_p$$ l p -norm load balancing with buffer or rearrangements," 4OR, Springer, vol. 15(3), pages 265-276, September.
    6. Feifeng Zheng & Yuhong Chen & Ming Liu & Yinfeng Xu, 2022. "Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1060-1076, September.
    7. Xing Chai & Wenhua Li & Yuejuan Zhu, 2021. "Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine," Annals of Operations Research, Springer, vol. 298(1), pages 79-93, March.
    8. Emine Akyol Ozer & Tugba Sarac, 2019. "MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(1), pages 94-124, April.
    9. Leah Epstein, 2018. "A survey on makespan minimization in semi-online environments," Journal of Scheduling, Springer, vol. 21(3), pages 269-284, June.

    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. Leung, Joseph Y.-T. & Li, Chung-Lun, 2016. "Scheduling with processing set restrictions: A literature update," International Journal of Production Economics, Elsevier, vol. 175(C), pages 1-11.
    2. Jueliang Hu & Yiwei Jiang & Ping Zhou & An Zhang & Qinghui Zhang, 2017. "Total completion time minimization in online hierarchical scheduling of unit-size jobs," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 866-881, April.
    3. An Zhang & Yiwei Jiang & Lidan Fan & Jueliang Hu, 2015. "Optimal online algorithms on two hierarchical machines with tightly-grouped processing times," Journal of Combinatorial Optimization, Springer, vol. 29(4), pages 781-795, May.
    4. Xianglai Qi & Jinjiang Yuan, 2017. "Semi-online hierarchical scheduling for $$l_p$$ l p -norm load balancing with buffer or rearrangements," 4OR, Springer, vol. 15(3), pages 265-276, September.
    5. Karhi, Shlomo & Shabtay, Dvir, 2014. "Online scheduling of two job types on a set of multipurpose machines," International Journal of Production Economics, Elsevier, vol. 150(C), pages 155-162.
    6. Xianglai Qi & Jinjiang Yuan, 2019. "Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(01), pages 1-16, February.
    7. Wu, Yong & Ji, Min & Yang, Qifan, 2012. "Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision," International Journal of Production Economics, Elsevier, vol. 135(1), pages 367-371.
    8. Islam Akaria & Leah Epstein, 2023. "Bin stretching with migration on two hierarchical machines," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 98(1), pages 111-153, August.
    9. Islam Akaria & Leah Epstein, 2022. "Online scheduling with migration on two hierarchical machines," Journal of Combinatorial Optimization, Springer, vol. 44(5), pages 3535-3548, December.
    10. Lee, Kangbok & Hwang, Hark-Chin & Lim, Kyungkuk, 2014. "Semi-online scheduling with GoS eligibility constraints," International Journal of Production Economics, Elsevier, vol. 153(C), pages 204-214.
    11. Huiqiao Su & Michael Pinedo & Guohua Wan, 2017. "Parallel machine scheduling with eligibility constraints: A composite dispatching rule to minimize total weighted tardiness," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(3), pages 249-267, April.
    12. Ferreira, Cristiane & Figueira, Gonçalo & Amorim, Pedro, 2021. "Scheduling Human-Robot Teams in collaborative working cells," International Journal of Production Economics, Elsevier, vol. 235(C).
    13. Chuleeporn Kusoncum & Kanchana Sethanan & Richard F. Hartl & Thitipong Jamrus, 2022. "Modified differential evolution and heuristic algorithms for dump tippler machine allocation in a typical sugar mill in Thailand," Operational Research, Springer, vol. 22(5), pages 5863-5895, November.
    14. Li, Shuguang, 2017. "Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan," European Journal of Operational Research, Elsevier, vol. 260(1), pages 12-20.
    15. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    16. Li, Chung-Lun & Wang, Xiuli, 2010. "Scheduling parallel machines with inclusive processing set restrictions and job release times," European Journal of Operational Research, Elsevier, vol. 200(3), pages 702-710, February.
    17. Epstein, Leah & Levin, Asaf, 2011. "Scheduling with processing set restrictions: PTAS results for several variants," International Journal of Production Economics, Elsevier, vol. 133(2), pages 586-595, October.
    18. André Rossi & Alexis Aubry & Mireille Jacomino, 2011. "A sensitivity analysis to assess the completion time deviation for multi-purpose machines facing demand uncertainty," Annals of Operations Research, Springer, vol. 191(1), pages 219-249, November.
    19. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    20. Zhiyi Tan & An Zhang, 2010. "A note on hierarchical scheduling on two uniform machines," Journal of Combinatorial Optimization, Springer, vol. 20(1), pages 85-95, July.

    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:204:y:2013:i:1:p:189-222:10.1007/s10479-012-1271-6. 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.