IDEAS home Printed from https://ideas.repec.org/a/hin/jnddns/805294.html
   My bibliography  Save this article

Online Scheduling on a Single Machine with Grouped Processing Times

Author

Listed:
  • Qijia Liu
  • Long Wan
  • Lijun Wei

Abstract

We consider the online scheduling problem on a single machine with the assumption that all jobs have their processing times in , where and . All jobs arrive over time, and each job and its processing time become known at its arrival time. The jobs should be first processed on a single machine and then delivered by a vehicle to some customer. When the capacity of the vehicle is infinite, we provide an online algorithm with the best competitive ratio of . When the capacity of the vehicle is finite, that is, the vehicle can deliver at most c jobs at a time, we provide another best possible online algorithm with the competitive ratio of .

Suggested Citation

  • Qijia Liu & Long Wan & Lijun Wei, 2015. "Online Scheduling on a Single Machine with Grouped Processing Times," Discrete Dynamics in Nature and Society, Hindawi, vol. 2015, pages 1-7, April.
    • Handle: RePEc:hin:jnddns:805294
    DOI: 10.1155/2015/805294
    as

    Download full text from publisher

    File URL: http://downloads.hindawi.com/journals/DDNS/2015/805294.pdf
    Download Restriction: no
    File URL: http://downloads.hindawi.com/journals/DDNS/2015/805294.xml
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2015/805294?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
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. 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.

    More about this item

    Statistics

    Access and download statistics

    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:hin:jnddns:805294. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Mohamed Abdelhakeem (email available below). General contact details of provider: https://www.hindawi.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.