Two-Machine Job-Shop Scheduling with Equal Processing Times on Each Machine

Evgeny Gafarov and Frank Werner
Additional contact information
Evgeny Gafarov: V.A. Trapeznikov Institute of Control Sciences of the Russian Academy of Sciences, Profsoyuznaya st. 65, 117997 Moscow, Russia
Frank Werner: Fakultät für Mathematik, Otto-von-Guericke-Universität Magdeburg, PSF 4120, 39016 Magdeburg, Germany

Mathematics, 2019, vol. 7, issue 3, 1-11

Abstract: In this paper, we consider a two-machine job-shop scheduling problem of minimizing total completion time subject to n jobs with two operations and equal processing times on each machine. This problem occurs e.g., as a single-track railway scheduling problem with three stations and constant travel times between any two adjacent stations. We present a polynomial dynamic programming algorithm of the complexity O ( n 5 ) and a heuristic procedure of the complexity O ( n 3 ) . This settles the complexity status of the problem under consideration which was open before and extends earlier work for the two-station single-track railway scheduling problem. We also present computational results of the comparison of both algorithms. For the 30,000 instances with up to 30 jobs considered, the average relative error of the heuristic is less than 1 % . In our tests, the practical running time of the dynamic programming algorithm was even bounded by O ( n 4 ) .

Keywords: scheduling; total completion time; job-shop (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/3/301/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/3/301/ (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:7:y:2019:i:3:p:301-:d:216886

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 ().