Two-Machine Job-Shop Scheduling with Equal Processing Times on Each Machine
Open Access
- 25 March 2019
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 7 (3), 301
- https://doi.org/10.3390/math7030301
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 and a heuristic procedure of the complexity . 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 . In our tests, the practical running time of the dynamic programming algorithm was even bounded by .
Keywords
Funding Information
- Deutscher Akademischer Austauschdienst (91695276)
- Russian Foundation for Basic Research (18-07-00656)
This publication has 22 references indexed in Scilit:
- A Permutation-Based Neighborhood for the Blocking Job-Shop Problem with Total Tardiness MinimizationOperations Research Proceedings, 2018
- Approaches to modeling train scheduling problems as job-shop problems with blocking constraintsJournal of Scheduling, 2017
- Two-station single-track railway scheduling problem with trains of equal speedComputers & Industrial Engineering, 2015
- Parallel machine problems with equal processing times: a surveyJournal of Scheduling, 2011
- A disjunctive graph model and framework for constructing new train schedulesEuropean Journal of Operational Research, 2010
- Scheduling equal-length jobs on identical parallel machinesDiscrete Applied Mathematics, 2000
- Is a unit-time job shop not easier than identical parallel machines?Discrete Applied Mathematics, 1998
- Total completion time minimization in two-machine job shops with unit-time operationsEuropean Journal of Operational Research, 1996
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a SurveyAnnals of Discrete Mathematics, 1979
- An extension of Johnson's results on job IDT schedulingNaval Research Logistics Quarterly, 1956