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

Optimal algorithms for single-machine scheduling with rejection to minimize the makespan

Author

Listed:
  • Lu, Lingfa
  • Ng, C.T.
  • Zhang, Liqi

Abstract

In this paper we consider the single-machine scheduling problem with rejection. Each job has an arrival time, a processing time and a rejection penalty. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. First, we present a polynomial-time algorithm for the off-line problem when split is allowed. Second, for the on-line problem with arbitrary arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio 2. Finally, for the on-line problem with at most two distinct arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio .

Suggested Citation

  • Lu, Lingfa & Ng, C.T. & Zhang, Liqi, 2011. "Optimal algorithms for single-machine scheduling with rejection to minimize the makespan," International Journal of Production Economics, Elsevier, vol. 130(2), pages 153-158, April.
    • Handle: RePEc:eee:proeco:v:130:y:2011:i:2:p:153-158
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925-5273(10)00472-X
    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. Og[breve]uz, Ceyda & Sibel Salman, F. & Bilgintürk YalçIn, Zehra, 2010. "Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, Elsevier, vol. 125(1), pages 200-211, May.
    2. György Dósa & Yong He, 2006. "Scheduling with machine cost and rejection," Journal of Combinatorial Optimization, Springer, vol. 12(4), pages 337-350, December.
    3. Nait Tahar, Djamel & Yalaoui, Farouk & Chu, Chengbin & Amodeo, Lionel, 2006. "A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 63-73, February.
    4. Zhang, Liqi & Lu, Lingfa & Yuan, Jinjiang, 2009. "Single machine scheduling with release dates and rejection," European Journal of Operational Research, Elsevier, vol. 198(3), pages 975-978, November.
    5. Cheng, Yushao & Sun, Shijie, 2009. "Scheduling linear deteriorating jobs with rejection on a single machine," European Journal of Operational Research, Elsevier, vol. 194(1), pages 18-27, 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. Xianzhao Zhang & Dachuan Xu & Donglei Du & Chenchen Wu, 2018. "Approximation algorithms for precedence-constrained identical machine scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 35(1), pages 318-330, January.
    2. Peihai Liu & Xiwen Lu, 2020. "New approximation algorithms for machine scheduling with rejection on single and parallel machine," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 929-952, November.
    3. Liqi Zhang & Lingfa Lu & Shisheng Li, 2016. "New results on two-machine flow-shop scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1493-1504, May.
    4. Cheng He & Joseph Y.-T. Leung & Kangbok Lee & Michael L. Pinedo, 2016. "Improved algorithms for single machine scheduling with release dates and rejections," 4OR, Springer, vol. 14(1), pages 41-55, March.
    5. 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.
    6. Guojun Hu & Pengxiang Pan & Suding Liu & Ping Yang & Runtao Xie, 2024. "The prize-collecting single machine scheduling with bounds and penalties," Journal of Combinatorial Optimization, Springer, vol. 48(2), pages 1-13, September.
    7. Xiaofei Liu & Man Xiao & Weidong Li & Yaoyu Zhu & Lei Ma, 2023. "Algorithms for single machine scheduling problem with release dates and submodular penalties," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-18, May.
    8. Ma, Ran & Guo, Sainan & Miao, Cuixia, 2021. "A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection," Applied Mathematics and Computation, Elsevier, vol. 392(C).
    9. Liqi Zhang & Lingfa Lu, 2016. "Parallel-machine scheduling with release dates and rejection," 4OR, Springer, vol. 14(2), pages 165-172, June.
    10. Liu, Zhixin & Lu, Liang & Qi, Xiangtong, 2020. "Price quotation for orders with different due dates," International Journal of Production Economics, Elsevier, vol. 220(C).
    11. Ran Ma & Jinjiang Yuan, 2017. "Online scheduling to minimize the total weighted completion time plus the rejection cost," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 483-503, August.
    12. Ma, Ran & Guo, Sainan, 2021. "Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 290(1), pages 57-67.

    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. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    2. Zhong, Xueling & Ou, Jinwen & Wang, Guoqing, 2014. "Order acceptance and scheduling with machine availability constraints," European Journal of Operational Research, Elsevier, vol. 232(3), pages 435-441.
    3. Liqi Zhang & Lingfa Lu, 2016. "Parallel-machine scheduling with release dates and rejection," 4OR, Springer, vol. 14(2), pages 165-172, June.
    4. Ou, Jinwen & Zhong, Xueling & Wang, Guoqing, 2015. "An improved heuristic for parallel machine scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 241(3), pages 653-661.
    5. Jinwen Ou & Xueling Zhong, 2017. "Order acceptance and scheduling with consideration of service level," Annals of Operations Research, Springer, vol. 248(1), pages 429-447, January.
    6. Og[breve]uz, Ceyda & Sibel Salman, F. & Bilgintürk YalçIn, Zehra, 2010. "Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, Elsevier, vol. 125(1), pages 200-211, May.
    7. Tarhan, İstenç & Oğuz, Ceyda, 2022. "A matheuristic for the generalized order acceptance and scheduling problem," European Journal of Operational Research, Elsevier, vol. 299(1), pages 87-103.
    8. Zhang, Liqi & Lu, Lingfa & Yuan, Jinjiang, 2009. "Single machine scheduling with release dates and rejection," European Journal of Operational Research, Elsevier, vol. 198(3), pages 975-978, November.
    9. Xiao, Yiyong & Yuan, Yingying & Zhang, Ren-Qian & Konak, Abdullah, 2015. "Non-permutation flow shop scheduling with order acceptance and weighted tardiness," Applied Mathematics and Computation, Elsevier, vol. 270(C), pages 312-333.
    10. Ma, Ran & Guo, Sainan, 2021. "Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 290(1), pages 57-67.
    11. Peihai Liu & Xiwen Lu, 2020. "New approximation algorithms for machine scheduling with rejection on single and parallel machine," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 929-952, November.
    12. Mohamadreza Dabiri & Mehdi Yazdani & Bahman Naderi & Hassan Haleh, 2022. "Modeling and solution methods for hybrid flow shop scheduling problem with job rejection," Operational Research, Springer, vol. 22(3), pages 2721-2765, July.
    13. Xueling Zhong & Zhangming Pan & Dakui Jiang, 2017. "Scheduling with release times and rejection on two parallel machines," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 934-944, April.
    14. Simon Thevenin & Nicolas Zufferey & Rémy Glardon, 2017. "Model and metaheuristics for a scheduling problem integrating procurement, sale and distribution decisions," Annals of Operations Research, Springer, vol. 259(1), pages 437-460, December.
    15. de Weerdt, Mathijs & Baart, Robert & He, Lei, 2021. "Single-machine scheduling with release times, deadlines, setup times, and rejection," European Journal of Operational Research, Elsevier, vol. 291(2), pages 629-639.
    16. Koulamas, Christos & Kyparisis, George J., 2023. "A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 305(3), pages 999-1017.
    17. Liu, Zhixin & Lu, Liang & Qi, Xiangtong, 2020. "Price quotation for orders with different due dates," International Journal of Production Economics, Elsevier, vol. 220(C).
    18. Du-Juan Wang & Yunqiang Yin & Mengqi Liu, 2016. "Bicriteria scheduling problems involving job rejection, controllable processing times and rate-modifying activity," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3691-3705, June.
    19. Gur Mosheiov & Assaf Sarig & Vitaly Strusevich, 2020. "Minmax scheduling and due-window assignment with position-dependent processing times and job rejection," 4OR, Springer, vol. 18(4), pages 439-456, December.
    20. Wang, Xiuli & Cheng, T.C.E., 2015. "A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint," International Journal of Production Economics, Elsevier, vol. 161(C), pages 74-82.

    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:130:y:2011:i:2:p:153-158. 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.