50821

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

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

Электронная публикация: 

Да

ISBN/ISSN: 

2227-7390

DOI: 

10.3390/math7030301

Наименование источника: 

  • Mathematics

Обозначение и номер тома: 

7(3), 301

Город: 

  • Basel

Издательство: 

  • MDPI

Год издания: 

2019

Страницы: 

https://www.mdpi.com/2227-7390/7/3/301
Аннотация
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(n5) and a heuristic procedure of the complexity O(n3). 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(n4)

Библиографическая ссылка: 

Гафаров Е.Р., Werner F.?. Two-Machine Job-Shop Scheduling with Equal Processing Times on Each Machine // Mathematics. 2019. 7(3), 301. С. https://www.mdpi.com/2227-7390/7/3/301.