IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v273y2016icp570-583.html
   My bibliography  Save this article

Online scheduling with linear deteriorating jobs to minimize the total weighted completion time

Author

Listed:
  • Ma, Ran
  • Tao, Jiping
  • Yuan, Jinjiang

Abstract

In this paper, we study the online scheduling of linear deteriorating jobs on a single machine to minimize the total weighted completion time. In the problem, a set of n independent linear deteriorating jobs arriving online over time has to be scheduled on a single machine, where the information of each job including its deterioration rate and weight is unknown in advance. Linear deterioration means that the processing time pj of a job Jj is a linear function of its starting time sj. In this paper, we assume that pj=αj(A+Bsj), where A and B are nonnegative with A+B>0 and αj ≥ 0 is the deterioration rate of Jj. The goal is to minimize the total weighted completion time, i.e., ∑wjCj. For this problem, we provide a best possible online algorithm with a competitive ratio of 1+λ(A)+αmaxB, where αmax=max1≤j≤nαj and λ(A)=0 or λ(A)=1 depending on whether A=0 or A > 0.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:apmaco:v:273:y:2016:i:c:p:570-583
    DOI: 10.1016/j.amc.2015.10.058
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300315014095
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2015.10.058?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. Rustogi, Kabir & Strusevich, Vitaly A., 2012. "Single machine scheduling with general positional deterioration and rate-modifying maintenance," Omega, Elsevier, vol. 40(6), pages 791-804.
    2. J-B Wang & Z-Q Xia, 2006. "Flow shop scheduling problems with deteriorating jobs under dominating machines," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(2), pages 220-226, February.
    3. Wang, Ji-Bo & Xia, Zun-Quan, 2006. "Flow shop scheduling with deteriorating jobs under dominating machines," Omega, Elsevier, vol. 34(4), pages 327-336, August.
    4. Gawiejnowicz, Stanislaw & Kononov, Alexander, 2010. "Complexity and approximability of scheduling resumable proportionally deteriorating jobs," European Journal of Operational Research, Elsevier, vol. 200(1), pages 305-308, January.
    5. 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.
    6. Sid Browne & Uri Yechiali, 1990. "Scheduling Deteriorating Jobs on a Single Processor," Operations Research, INFORMS, vol. 38(3), pages 495-498, June.
    7. Edward J. Anderson & Chris N. Potts, 2004. "Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time," Mathematics of Operations Research, INFORMS, vol. 29(3), pages 686-697, August.
    8. Leslie A. Hall & Andreas S. Schulz & David B. Shmoys & Joel Wein, 1997. "Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 22(3), pages 513-544, August.
    9. Li, Shisheng & Ng, C.T. & Cheng, T.C.E. & Yuan, Jinjiang, 2011. "Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 210(3), pages 482-488, May.
    10. Cheng, T. C. E. & Ding, Q. & Lin, B. M. T., 2004. "A concise survey of scheduling with time-dependent processing times," European Journal of Operational Research, Elsevier, vol. 152(1), pages 1-13, January.
    11. B Alidaee & N K Womer, 1999. "Scheduling with time dependent processing times: Review and extensions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(7), pages 711-720, July.
    12. Ma, Ran & Yuan, Jinjiang, 2014. "Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time," International Journal of Production Economics, Elsevier, vol. 158(C), pages 114-119.
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Xing Chai & Wenhua Li & Yuejuan Zhu, 2021. "Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine," Annals of Operations Research, Springer, vol. 298(1), pages 79-93, March.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Wang, Ling & Sun, Lin-Yan & Sun, Lin-Hui & Wang, Ji-Bo, 2010. "On three-machine flow shop scheduling with deteriorating jobs," International Journal of Production Economics, Elsevier, vol. 125(1), pages 185-189, May.
    6. Sawik, Tadeusz, 2010. "An integer programming approach to scheduling in a contaminated area," Omega, Elsevier, vol. 38(3-4), pages 179-191, June.
    7. Cheng, Mingbao & Tadikamalla, Pandu R. & Shang, Jennifer & Zhang, Shaqing, 2014. "Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs," European Journal of Operational Research, Elsevier, vol. 234(3), pages 650-657.
    8. Wang, Ting & Baldacci, Roberto & Lim, Andrew & Hu, Qian, 2018. "A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine," European Journal of Operational Research, Elsevier, vol. 271(3), pages 826-838.
    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. 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.
    11. 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.
    12. Wang, Xiuli & Edwin Cheng, T.C., 2007. "Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 178(1), pages 57-70, April.
    13. 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.
    14. Xing Chai & Wenhua Li & Hang Yuan & Libo Wang, 2022. "Online scheduling on a single machine with linear deteriorating processing times and delivery times," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1900-1912, October.
    15. 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.
    16. 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.
    17. Wang, Ji-Bo, 2007. "Single-machine scheduling problems with the effects of learning and deterioration," Omega, Elsevier, vol. 35(4), pages 397-402, August.
    18. Min Kong & Xinbao Liu & Jun Pei & Panos M. Pardalos & Nenad Mladenovic, 2020. "Parallel-batching scheduling with nonlinear processing times on a single and unrelated parallel machines," Journal of Global Optimization, Springer, vol. 78(4), pages 693-715, December.
    19. Xing Chai & Wenhua Li & Hang Yuan & Libo Wang, 0. "Online scheduling on a single machine with linear deteriorating processing times and delivery times," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-13.
    20. Dar-Li Yang & Wen-Hung Kuo, 2009. "Single-machine scheduling with both deterioration and learning effects," Annals of Operations Research, Springer, vol. 172(1), pages 315-327, November.

    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:apmaco:v:273:y:2016:i:c:p:570-583. 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: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.