|
Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 2006, Volume 13, Issue 3, Pages 83–102
(Mi da37)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
Some properties of optimal schedules for the Johnson problem with preemption
S. V. Sevast'yanov, D. A. Chemisova, I. D. Chernykh Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
The properties are under study of the optimal schedules for the NP-hard Johnson problem with preemption. The length of an optimal schedule is shown to coincide with the total length of some subset of operations. These properties demonstrate that the optimal schedule of every instance of the problem can be found by a greedy algorithm (for the properly defined priority orders of operations on machines). This yields the first exact algorithm for the problem known since 1978. It is shown that the number of interruptions in a greedy schedule (and therefore, in the optimal schedule) is at most the number of operations, which is significantly better than the available upper bounds on the number of interruptions in the optimal schedule.
Citation:
S. V. Sevast'yanov, D. A. Chemisova, I. D. Chernykh, “Some properties of optimal schedules for the Johnson problem with preemption”, Diskretn. Anal. Issled. Oper., Ser. 1, 13:3 (2006), 83–102; J. Appl. Industr. Math., 1:3 (2007), 386–397
Linking options:
https://www.mathnet.ru/eng/da37 https://www.mathnet.ru/eng/da/v13/s1/i3/p83
|
Statistics & downloads: |
Abstract page: | 719 | Full-text PDF : | 170 | References: | 48 |
|