Branch Less, Cut More and Schedule Jobs with Release and Delivery Times on Uniform Machines

Nodari Vakhania and Frank Werner
Additional contact information
Nodari Vakhania: Centro de Investigacion en Ciences, Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, Mexico
Frank Werner: Faculty of Mathemaics, Otto-von-Guericke University Magdeburg, PSF 4120, 39016 Magdeburg, Germany

Mathematics, 2021, vol. 9, issue 6, 1-18

Abstract: We consider the problem of scheduling n jobs with identical processing times and given release as well as delivery times on m uniform machines. The goal is to minimize the makespan, i.e., the maximum full completion time of any job. This problem is well-known to have an open complexity status even if the number of jobs is fixed. We present a polynomial-time algorithm for the problem which is based on the earlier introduced algorithmic framework blesscmore (“branch less and cut more”). We extend the analysis of the so-called behavior alternatives developed earlier for the version of the problem with identical parallel machines and show how the earlier used technique for identical machines can be extended to the uniform machine environment if a special condition on the job parameters is imposed. The time complexity of the proposed algorithm is O ( γ m 2 n log n ) , where γ can be either n or the maximum job delivery time q max . This complexity can even be reduced further by using a smaller number κ < n in the estimation describing the number of jobs of particular types. However, this number κ becomes only known when the algorithm has terminated.

Keywords: scheduling; uniform machines; release time; delivery time; time complexity; algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/6/633/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/6/633/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:6:p:633-:d:518026

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().