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

Scheduling with processing set restrictions: PTAS results for several variants

Author

Listed:
  • Epstein, Leah
  • Levin, Asaf

Abstract

We consider multiprocessor scheduling to minimize makespan. Each job has a given processing time and in addition, a subset of machines associated with it, also called its processing set. Each job has to be assigned to one machine in its set, thus contributing to the load of this machine. We study two variants of this problem on identical machines, the case of nested processing sets, and the case of tree-hierarchical processing sets. In addition, we consider uniformly related machines with a special case of inclusive processing sets, which has a clear motivation. We design polynomial time approximation schemes for these three variants. The first case resolves one of the open problems stated in the survey by Leung and Li (2008).

Suggested Citation

  • 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.
    • Handle: RePEc:eee:proeco:v:133:y:2011:i:2:p:586-595
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S092552731100199X
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Weng, Michael X. & Lu, John & Ren, Haiying, 2001. "Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective," International Journal of Production Economics, Elsevier, vol. 70(3), pages 215-226, April.
    2. 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.
    3. 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.
    4. A A K Jeng & B M T Lin, 2007. "A note on parallel-machine scheduling with deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(6), pages 824-826, June.
    5. 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.
    6. Kang, Liying & Ng, C.T., 2007. "A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs," International Journal of Production Economics, Elsevier, vol. 109(1-2), pages 180-184, September.
    7. Liao, Ching-Jong & Lin, Chien-Hung, 2003. "Makespan minimization for two uniform parallel machines," International Journal of Production Economics, Elsevier, vol. 84(2), pages 205-213, May.
    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. 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.
    3. 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.
    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. "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. 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. Mosheiov, Gur, 2012. "A note: Multi-machine scheduling with general position-based deterioration to minimize total load," International Journal of Production Economics, Elsevier, vol. 135(1), pages 523-525.
    3. 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.
    4. J-B Wang & J-J Wang & P Ji, 2011. "Scheduling jobs with chain precedence constraints and deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(9), pages 1765-1770, September.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    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. 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.
    13. Ming Liu & Feifeng Zheng & Chengbin Chu & Jiantong Zhang, 2012. "An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration," Journal of Combinatorial Optimization, Springer, vol. 23(4), pages 483-492, May.
    14. Stanisław Gawiejnowicz, 2020. "A review of four decades of time-dependent scheduling: main results, new topics, and open problems," Journal of Scheduling, Springer, vol. 23(1), pages 3-47, February.
    15. 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.
    16. Su, Ling-Huey & Lien, Chun-Yuan, 2009. "Scheduling parallel machines with resource-dependent processing times," International Journal of Production Economics, Elsevier, vol. 117(2), pages 256-266, February.
    17. Wu, Chin-Chia & Lee, Wen-Chiung, 2008. "Single-machine group-scheduling problems with deteriorating setup times and job-processing times," International Journal of Production Economics, Elsevier, vol. 115(1), pages 128-133, September.
    18. Chou, Yon-Chun & Lin, Yue-Lan & Chun, King-Fai, 2014. "A construction of knowledge rules for reactive planning of job-mix assignment to homogeneous serial batch machines," International Journal of Production Economics, Elsevier, vol. 151(C), pages 56-66.
    19. Yalaoui, F. & Chu, C., 2006. "New exact method to solve the Pm/rj/[summation operator]Cj schedule problem," International Journal of Production Economics, Elsevier, vol. 100(1), pages 168-179, March.
    20. Daniel D. Zeng & J. Leon Zhao, 2005. "Effective Role Resolution in Workflow Management," INFORMS Journal on Computing, INFORMS, vol. 17(3), pages 374-387, August.

    More about this item

    Keywords

    Scheduling Approximation scheme;

    Statistics

    Access and download statistics

    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:133:y:2011:i:2:p:586-595. 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.