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

Scheduling with processing set restrictions: A literature update

Author

Listed:
  • Leung, Joseph Y.-T.
  • Li, Chung-Lun

Abstract

In 2008, we published a survey paper on machine scheduling with processing set restrictions [Leung, J.Y.-T., Li, C.-L., 2008. Scheduling with processing set restrictions: a survey. Int. J. Prod. Econ. 116 (2), 251–262]. Since the appearance of that survey paper, there has been a significant increase in interest in this field. In this paper, we provide an expository update of this line of research. Our survey covers five types of processing set restrictions, namely inclusive processing sets, nested processing sets, interval processing sets, tree-hierarchical processing sets, and arbitrary processing sets, and it covers both offline and online problems. While our main focus is on scheduling models with a makespan objective, other performance criteria are also discussed.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:proeco:v:175:y:2016:i:c:p:1-11
    DOI: 10.1016/j.ijpe.2014.09.038
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527316000190
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2014.09.038?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. Chung-Lun Li & Kangbok Lee, 2016. "A note on scheduling jobs with equal processing times and inclusive processing set restrictions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(1), pages 83-86, January.
    2. 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.
    3. Zhenbo Wang & Wenxun Xing, 2010. "Worst-case analysis for on-line service policies," Journal of Combinatorial Optimization, Springer, vol. 19(1), pages 107-122, January.
    4. Jia, Zhao-hong & Li, Kai & Leung, Joseph Y.-T., 2015. "Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities," International Journal of Production Economics, Elsevier, vol. 169(C), pages 1-10.
    5. Shan Wang & Huiqiao Su & Guohua Wan, 2015. "Resource-constrained machine scheduling with machine eligibility restriction and its applications to surgical operations scheduling," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 982-995, November.
    6. Xinrong Lu & Zhaohui Liu, 2015. "Online Hierarchical Scheduling on Two Uniform Machines with Bounded Job Sizes," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(05), pages 1-31.
    7. 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.
    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. Weidong Li & Jianping Li & Tongquan Zhang, 2012. "Two Approximation Schemes For Scheduling On Parallel Machines Under A Grade Of Service Provision," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 29(05), pages 1-12.
    10. 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.
    11. Shlomo Karhi & Dvir Shabtay, 2013. "On the optimality of the TLS algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines," Journal of Combinatorial Optimization, Springer, vol. 26(1), pages 198-222, July.
    12. 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.
    13. Wang, Jun-Qiang & Leung, Joseph Y.-T., 2014. "Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan," International Journal of Production Economics, Elsevier, vol. 156(C), pages 325-331.
    14. 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.
    15. 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.
    16. Chung-Lun Li & Qingying Li, 2015. "Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(3), pages 516-523, March.
    17. Recalde, D. & Rutten, C. & Schuurman, P. & Vredeveld, T., 2009. "Local search performance guarantees for restricted related parallel machine scheduling," Research Memorandum 061, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    18. 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.
    19. 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.
    20. 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.
    21. 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.
    22. 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.
    23. Xu, Dongsheng & Li, Chung-Lun & Leung, Joseph Y.-T., 2012. "Berth allocation with time-dependent physical limitations on vessels," European Journal of Operational Research, Elsevier, vol. 216(1), pages 47-56.
    24. 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.
    25. 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.
    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. Li, Weidong & Ou, Jinwen, 2024. "Approximation algorithms for scheduling parallel machines with an energy constraint in green manufacturing," European Journal of Operational Research, Elsevier, vol. 314(3), pages 882-893.
    2. Jinwen Ou & Xueling Zhong & Xiangtong Qi, 2016. "Scheduling parallel machines with inclusive processing set restrictions and job rejection," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(8), pages 667-681, December.
    3. 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.
    4. Leung, Joseph Y-T. & Ng, C.T., 2017. "Fast approximation algorithms for uniform machine scheduling with processing set restrictions," European Journal of Operational Research, Elsevier, vol. 260(2), pages 507-513.
    5. Li, Shuguang, 2017. "Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities," European Journal of Operational Research, Elsevier, vol. 263(3), pages 815-826.
    6. 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.

    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. 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.
    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. 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.
    4. Leung, Joseph Y-T. & Ng, C.T., 2017. "Fast approximation algorithms for uniform machine scheduling with processing set restrictions," European Journal of Operational Research, Elsevier, vol. 260(2), pages 507-513.
    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. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Li, Shuguang, 2017. "Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities," European Journal of Operational Research, Elsevier, vol. 263(3), pages 815-826.
    11. 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.
    12. 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.
    13. Jinwen Ou & Xueling Zhong & Xiangtong Qi, 2016. "Scheduling parallel machines with inclusive processing set restrictions and job rejection," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(8), pages 667-681, December.
    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. 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.
    16. 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.
    17. Goldberg, Noam & Karhi, Shlomo, 2019. "Online packing of arbitrary sized items into designated and multipurpose bins," European Journal of Operational Research, Elsevier, vol. 279(1), pages 54-67.
    18. 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.
    19. 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.
    20. Baoyu Liao & Qingru Song & Jun Pei & Shanlin Yang & Panos M. Pardalos, 2020. "Parallel-machine group scheduling with inclusive processing set restrictions, outsourcing option and serial-batching under the effect of step-deterioration," Journal of Global Optimization, Springer, vol. 78(4), pages 717-742, 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:175:y:2016:i:c:p:1-11. 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.