IDEAS home Printed from https://ideas.repec.org/a/taf/tprsxx/v61y2023i19p6434-6450.html
   My bibliography  Save this article

Stability of a schedule minimising the makespan for processing jobs on identical machines

Author

Listed:
  • Yuri N. Sotskov

Abstract

A set of jobs has to be processed on identical machines. Every job may be processed on any available machine without preemptions. The criterion is to minimise the makespan (i.e. the completion time of the last job in a schedule). During the realisation of a schedule, durations of some jobs may deviate from the initial values estimated before scheduling. Other jobs have fixed durations that are known before scheduling. We conduct a stability analysis of the optimal semi-active schedule. First, we derive necessary and sufficient conditions for an optimal schedule to be unstable with respect to infinitely small variations of the non-fixed durations (the stability radius of an unstable schedule is equal to zero). Second, we show that the stability radius of an optimal schedule could be infinitely large. Furthermore, several lower and upper bounds on the stability radius have been established. Third, we derive a formula and develop an algorithm for calculating stability radii.

Suggested Citation

  • Yuri N. Sotskov, 2023. "Stability of a schedule minimising the makespan for processing jobs on identical machines," International Journal of Production Research, Taylor & Francis Journals, vol. 61(19), pages 6434-6450, October.
    • Handle: RePEc:taf:tprsxx:v:61:y:2023:i:19:p:6434-6450
    DOI: 10.1080/00207543.2022.2128919
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2022.2128919
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/00207543.2022.2128919?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.

    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:taf:tprsxx:v:61:y:2023:i:19:p:6434-6450. 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: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TPRS20 .

    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.