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

Online Batch Scheduling of Simple Linear Deteriorating Jobs with Incompatible Families

Author

Listed:
  • Wenhua Li

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

  • Libo Wang

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

  • Xing Chai

    (College of Science, Henan University of Technology, Zhengzhou 450001, China)

  • Hang Yuan

    (Department of Economics, State University of New York at Binghamton, Binghamton, NY 13902, USA)

Abstract

We considered the online scheduling problem of simple linear deteriorating job families on m parallel batch machines to minimize the makespan, where the batch capacity is unbounded. In this paper, simple linear deteriorating jobs mean that the actual processing time p j of job J j is assumed to be a linear function of its starting time s j , i.e., p j = α j s j , where α j > 0 is the deterioration rate. Job families mean that one job must belong to some job family, and jobs of different families cannot be processed in the same batch. When m = 1 , we provide the best possible online algorithm with the competitive ratio of ( 1 + α max ) f , where f is the number of job families and α max is the maximum deterioration rate of all jobs. When m ≥ 1 and m = f , we provide the best possible online algorithm with the competitive ratio of 1 + α max .

Suggested Citation

  • Wenhua Li & Libo Wang & Xing Chai & Hang Yuan, 2020. "Online Batch Scheduling of Simple Linear Deteriorating Jobs with Incompatible Families," Mathematics, MDPI, vol. 8(2), pages 1-12, February.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:2:p:170-:d:315117
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Alessandro Agnetis & Jean-Charles Billaut & Stanisław Gawiejnowicz & Dario Pacciarelli & Ameur Soukhal, 2014. "Multiagent Scheduling," Springer Books, Springer, edition 127, number 978-3-642-41880-8, October.
    2. Kunnathur, Anand S. & Gupta, Sushil K., 1990. "Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem," European Journal of Operational Research, Elsevier, vol. 47(1), pages 56-64, July.
    3. Ji, Min & Cheng, T.C.E., 2010. "Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan," European Journal of Operational Research, Elsevier, vol. 202(1), pages 90-98, April.
    4. Vitaly A. Strusevich & Kabir Rustogi, 2017. "Scheduling with Time-Changing Effects and Rate-Modifying Activities," International Series in Operations Research and Management Science, Springer, number 978-3-319-39574-6, April.
    5. Alessandro Agnetis & Jean-Charles Billaut & Stanisław Gawiejnowicz & Dario Pacciarelli & Ameur Soukhal, 2014. "Multiagent Scheduling Fundamentals," Springer Books, in: Multiagent Scheduling, edition 127, chapter 0, pages 1-22, Springer.
    6. Ma, Ran & Tao, Jiping & Yuan, Jinjiang, 2016. "Online scheduling with linear deteriorating jobs to minimize the total weighted completion time," Applied Mathematics and Computation, Elsevier, vol. 273(C), pages 570-583.
    7. Sid Browne & Uri Yechiali, 1990. "Scheduling Deteriorating Jobs on a Single Processor," Operations Research, INFORMS, vol. 38(3), pages 495-498, June.
    8. Gawiejnowicz, Stanislaw, 2007. "Scheduling deteriorating jobs subject to job or machine availability constraints," European Journal of Operational Research, Elsevier, vol. 180(1), pages 472-478, July.
    9. Stanisław Gawiejnowicz & Alexander Kononov, 2014. "Isomorphic scheduling problems," Annals of Operations Research, Springer, vol. 213(1), pages 131-145, February.
    10. Vitaly A. Strusevich & Kabir Rustogi, 2017. "Scheduling with Rate-Modifying Activities," International Series in Operations Research & Management Science, in: Scheduling with Time-Changing Effects and Rate-Modifying Activities, chapter 0, pages 317-331, Springer.
    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. Rong-Rong Mao & Yi-Chun Wang & Dan-Yang Lv & Ji-Bo Wang & Yuan-Yuan Lu, 2023. "Delivery Times Scheduling with Deterioration Effects in Due Window Assignment Environments," Mathematics, MDPI, vol. 11(18), pages 1-18, September.

    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. 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.
    2. Rubing Chen & Jinjiang Yuan, 2020. "Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices," 4OR, Springer, vol. 18(2), pages 177-196, June.
    3. Zhongyi Jiang & Fangfang Chen & Xiandong Zhang, 2022. "Single-machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 116-139, January.
    4. Delorme, Maxence & Iori, Manuel & Mendes, Nilson F.M., 2021. "Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events," European Journal of Operational Research, Elsevier, vol. 295(3), pages 823-837.
    5. Shi-Sheng Li & Ren-Xia Chen & Qi Feng & Cheng-Wen Jiao, 2019. "Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 957-971, October.
    6. Helmut A. Sedding, 2020. "Scheduling jobs with a V-shaped time-dependent processing time," Journal of Scheduling, Springer, vol. 23(6), pages 751-768, December.
    7. W-H Kuo & D-L Yang, 2008. "A note on due-date assignment and single-machine scheduling with deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 857-859, June.
    8. C-C He & C-C Wu & W-C Lee, 2009. "Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1759-1766, December.
    9. Wu, Chin-Chia & Lee, Wen-Chiung, 2006. "Two-machine flowshop scheduling to minimize mean flow time under linear deterioration," International Journal of Production Economics, Elsevier, vol. 103(2), pages 572-584, October.
    10. Min Ji & Chou-Jung Hsu & Dar-Li Yang, 2013. "Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration," Journal of Combinatorial Optimization, Springer, vol. 26(3), pages 437-447, October.
    11. Shakeri, Shakib & Logendran, Rasaratnam, 2007. "A mathematical programming-based scheduling framework for multitasking environments," European Journal of Operational Research, Elsevier, vol. 176(1), pages 193-209, January.
    12. Aarabi, Fatemeh & Batta, Rajan, 2020. "Scheduling spatially distributed jobs with degradation: Application to pothole repair," Socio-Economic Planning Sciences, Elsevier, vol. 72(C).
    13. Qian, Jianbo & Steiner, George, 2013. "Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine," European Journal of Operational Research, Elsevier, vol. 225(3), pages 547-551.
    14. Shen, Zuo-Jun Max & Xie, Jingui & Zheng, Zhichao & Zhou, Han, 2023. "Dynamic scheduling with uncertain job types," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1047-1060.
    15. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    16. Baruch Mor, 2023. "Single machine scheduling problems involving job-dependent step-deterioration dates and job rejection," Operational Research, Springer, vol. 23(1), pages 1-19, March.
    17. Bachman, Aleksander & Janiak, Adam, 2000. "Minimizing maximum lateness under linear deterioration," European Journal of Operational Research, Elsevier, vol. 126(3), pages 557-566, November.
    18. Alan J. Soper & Vitaly A. Strusevich, 2020. "Refined conditions for V-shaped optimal sequencing on a single machine to minimize total completion time under combined effects," Journal of Scheduling, Springer, vol. 23(6), pages 665-680, December.
    19. Stanisław Gawiejnowicz & Wiesław Kurc, 2020. "New results for an open time-dependent scheduling problem," Journal of Scheduling, Springer, vol. 23(6), pages 733-744, December.
    20. Wang, Ji-Bo, 2007. "Single-machine scheduling problems with the effects of learning and deterioration," Omega, Elsevier, vol. 35(4), pages 397-402, August.

    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:8:y:2020:i:2:p:170-:d:315117. 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.