IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v7y2019i8p668-d251924.html
   My bibliography  Save this article

Single-Machine Scheduling with Rejection and an Operator Non-Availability Interval

Author

Listed:
  • Lili Zuo

    (School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China)

  • Zhenxia Sun

    (School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China)

  • Lingfa Lu

    (School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China)

  • Liqi Zhang

    (College of Information and Management Science, Henan Agricultural University, Zhengzhou 450002, China)

Abstract

In this paper, we study two scheduling problems on a single machine with rejection and an operator non-availability interval. In the operator non-availability interval, no job can be started or be completed. However, a crossover job is allowed such that it can be started before this interval and completed after this interval. Furthermore, we also assume that job rejection is allowed. That is, each job is either accepted and processed in-house, or is rejected by paying a rejection cost. Our task is to minimize the sum of the makespan (or the total weighted completion time) of accepted jobs and the total rejection cost of rejected jobs. For two scheduling problems with different objective functions, by borrowing the previous algorithms in the literature, we propose a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme (FPTAS), respectively.

Suggested Citation

  • Lili Zuo & Zhenxia Sun & Lingfa Lu & Liqi Zhang, 2019. "Single-Machine Scheduling with Rejection and an Operator Non-Availability Interval," Mathematics, MDPI, vol. 7(8), pages 1-8, July.
    • Handle: RePEc:gam:jmathe:v:7:y:2019:i:8:p:668-:d:251924
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/7/8/668/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/7/8/668/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Burdett, R.L. & Kozan, E., 2009. "Techniques for inserting additional trains into existing timetables," Transportation Research Part B: Methodological, Elsevier, vol. 43(8-9), pages 821-836, September.
    2. Imed Kacem & Hans Kellerer & Maryam Seifaddini, 2016. "Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 970-981, October.
    3. Liao, Ching-Jong & Shyur, Der-Lin & Lin, Chien-Hung, 2005. "Makespan minimization for two parallel machines with an availability constraint," European Journal of Operational Research, Elsevier, vol. 160(2), pages 445-456, January.
    4. Schmidt, Gunter, 2000. "Scheduling with limited machine availability," European Journal of Operational Research, Elsevier, vol. 121(1), pages 1-15, February.
    5. Aggoune, Riad, 2004. "Minimizing the makespan for the flow shop scheduling problem with availability constraints," European Journal of Operational Research, Elsevier, vol. 153(3), pages 534-543, March.
    6. Imed Kacem, 2009. "Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval," Journal of Combinatorial Optimization, Springer, vol. 17(2), pages 117-133, February.
    7. J. Breit & G. Schmidt & V. A. Strusevich, 2003. "Non-preemptive two-machine open shop scheduling with non-availability constraints," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 57(2), pages 217-234, May.
    8. Chuanli Zhao & Hengyong Tang, 2014. "Single Machine Scheduling with an Availability Constraint and Rejection," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 31(05), pages 1-15.
    9. 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.
    10. 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.
    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. Xinyu Sun & Tao Liu & Xin-Na Geng & Yang Hu & Jing-Xiao Xu, 2023. "Optimization of scheduling problems with deterioration effects and an optional maintenance activity," Journal of Scheduling, Springer, vol. 26(3), pages 251-266, June.
    2. Baruch Mor & Dana Shapira, 2022. "Single machine scheduling with non-availability interval and optional job rejection," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 480-497, August.

    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. Shabtay, Dvir, 2022. "Single-machine scheduling with machine unavailability periods and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 296(2), pages 423-439.
    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. Shabtay, Dvir & Zofi, Moshe, 2018. "Single machine scheduling with controllable processing times and an unavailability period to minimize the makespan," International Journal of Production Economics, Elsevier, vol. 198(C), pages 191-200.
    4. Seyed Habib A. Rahmati & Abbas Ahmadi & Kannan Govindan, 2018. "A novel integrated condition-based maintenance and stochastic flexible job shop scheduling problem: simulation-based optimization approach," Annals of Operations Research, Springer, vol. 269(1), pages 583-621, October.
    5. Shi-Sheng Li & Ren-Xia Chen, 2017. "Scheduling with Rejection and a Deteriorating Maintenance Activity on a Single Machine," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(02), pages 1-17, April.
    6. 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.
    7. Shi-Sheng Li & Ren-Xia Chen, 2022. "Minimizing total weighted late work on a single-machine with non-availability intervals," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1330-1355, September.
    8. 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.
    9. Ji Tian & Yan Zhou & Ruyan Fu, 2020. "An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown," Journal of Combinatorial Optimization, Springer, vol. 40(1), pages 170-180, July.
    10. Xiuli Wang & T. C. Edwin Cheng, 2007. "Machine scheduling with an availability constraint and job delivery coordination," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(1), pages 11-20, February.
    11. Fatima Benbouzid-Si Tayeb & Karima Benatchba & Abd-Essalam Messiaid, 2018. "Game theory-based integration of scheduling with flexible and periodic maintenance planning in the permutation flowshop sequencing problem," Operational Research, Springer, vol. 18(1), pages 221-255, April.
    12. Burdett, R.L. & Kozan, E., 2009. "Techniques for inserting additional trains into existing timetables," Transportation Research Part B: Methodological, Elsevier, vol. 43(8-9), pages 821-836, September.
    13. Shi-Sheng Li & De-Liang Qian & Ren-Xia Chen, 2017. "Proportionate Flow Shop Scheduling with Rejection," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(04), pages 1-13, August.
    14. Ren-Xia Chen & Shi-Sheng Li, 2020. "Minimizing maximum delivery completion time for order scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1044-1064, November.
    15. 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.
    16. 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.
    17. Detienne, Boris, 2014. "A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints," European Journal of Operational Research, Elsevier, vol. 235(3), pages 540-552.
    18. Imed Kacem & Hans Kellerer & Maryam Seifaddini, 2016. "Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 970-981, October.
    19. 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.
    20. Kacem, Imed & Chu, Chengbin, 2008. "Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint," International Journal of Production Economics, Elsevier, vol. 112(1), pages 138-150, March.

    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:gam:jmathe:v:7:y:2019:i:8:p:668-:d:251924. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.