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

Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time

Author

Listed:
  • Ma, Ran
  • Yuan, Jinjiang

Abstract

In this paper we introduce the concept of online tradeoff scheduling to minimize two objective functions f1 and f2 simultaneously. An online algorithm A is called (ρ1,ρ2)-competitive for minimizing f1 and f2 if A is ρ1-competitive for minimizing f1 and ρ2-competitive for minimizing f2. A (ρ1,ρ2)-competitive online algorithm A is called nondominated if there is no other (ρ1′,ρ2′)-competitive online algorithm A′ such that (ρ1′,ρ2′)≤(ρ1,ρ2) and either ρ1′<ρ1 or ρ2′<ρ2.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:proeco:v:158:y:2014:i:c:p:114-119
    DOI: 10.1016/j.ijpe.2014.07.027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527314002448
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2014.07.027?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. 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.
    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. 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.
    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. Qijia Liu & Jinjiang Yuan, 2016. "Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 385-395, August.
    2. 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.
    3. Li, Guo & Liu, Mengqi & Sethi, Suresh P. & Xu, Dehua, 2017. "Parallel-machine scheduling with machine-dependent maintenance periodic recycles," International Journal of Production Economics, Elsevier, vol. 186(C), pages 1-7.
    4. Wenhua Li & Weina Zhai & Xing Chai, 2019. "Online Bi-Criteria Scheduling on Batch Machines with Machine Costs," Mathematics, MDPI, vol. 7(10), pages 1-11, October.
    5. 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.

    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. 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.
    2. Yinfeng Xu & Rongteng Zhi & Feifeng Zheng & Ming Liu, 2022. "Competitive algorithm for scheduling of sharing machines with rental discount," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 414-434, August.
    3. 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.
    4. Jin Xu & Natarajan Gautam, 2020. "On competitive analysis for polling systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(6), pages 404-419, September.
    5. 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.
    6. 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.
    7. Liqi Zhang & Lingfa Lu, 2016. "Parallel-machine scheduling with release dates and rejection," 4OR, Springer, vol. 14(2), pages 165-172, June.
    8. 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.
    9. 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.
    10. Wenjie Li & Hailing Liu & Shisheng Li, 2018. "Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(04), pages 1-12, August.
    11. Goldberg, Noam & Karhi, Shlomo, 2019. "Online packing of arbitrary sized items into designated and multipurpose bins," European Journal of Operational Research, Elsevier, vol. 279(1), pages 54-67.
    12. Nicholas G. Hall & Marc E. Posner & Chris N. Potts, 2009. "Online Scheduling with Known Arrival Times," Mathematics of Operations Research, INFORMS, vol. 34(1), pages 92-102, February.
    13. Wenhua Li & Xing Chai, 2019. "The medical laboratory scheduling for weighted flow-time," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 83-94, January.
    14. A J Ruiz-Torres & F J López & P J Wojciechowski & J C Ho, 2010. "Parallel machine scheduling problems considering regular measures of performance and machine cost," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(5), pages 849-857, May.
    15. Goldberg, Noam & Karhi, Shlomo, 2017. "Packing into designated and multipurpose bins: A theoretical study and application to the cold chain," Omega, Elsevier, vol. 71(C), pages 85-92.
    16. Xiaoyan Zhang & Ran Ma & Jian Sun & Zan-Bo Zhang, 0. "Randomized selection algorithm for online stochastic unrelated machines scheduling," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-16.
    17. Ivo Blöchliger & Nicolas Zufferey, 2013. "Multi-coloring and job-scheduling with assignment and incompatibility costs," Annals of Operations Research, Springer, vol. 211(1), pages 83-101, December.
    18. Péter Györgyi & Tamás Kis & Tímea Tamási & József Békési, 2023. "Joint replenishment meets scheduling," Journal of Scheduling, Springer, vol. 26(1), pages 77-94, February.
    19. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    20. Xing Chai & Lingfa Lu & Wenhua Li & Liqi Zhang, 2018. "Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(06), pages 1-11, December.

    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:158:y:2014:i:c:p:114-119. 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.