Geodesic
Some properties of optimal schedules for the Johnson problem with preemption
Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 3, pp. 83-102.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2006_13_3_a5,
     author = {S. V. Sevast'yanov and D. A. Chemisova and I. D. Chernykh},
     title = {Some properties of optimal schedules for the {Johnson} problem with preemption},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {83--102},
     publisher = {mathdoc},
     volume = {13},
     number = {3},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2006_13_3_a5/}
}
TY  - JOUR
AU  - S. V. Sevast'yanov
AU  - D. A. Chemisova
AU  - I. D. Chernykh
TI  - Some properties of optimal schedules for the Johnson problem with preemption
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2006
SP  - 83
EP  - 102
VL  - 13
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2006_13_3_a5/
LA  - ru
ID  - DA_2006_13_3_a5
ER  - 
%0 Journal Article
%A S. V. Sevast'yanov
%A D. A. Chemisova
%A I. D. Chernykh
%T Some properties of optimal schedules for the Johnson problem with preemption
%J Diskretnyj analiz i issledovanie operacij
%D 2006
%P 83-102
%V 13
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2006_13_3_a5/
%G ru
%F DA_2006_13_3_a5
S. V. Sevast'yanov; D. A. Chemisova; I. D. Chernykh. Some properties of optimal schedules for the Johnson problem with preemption. Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 3, pp. 83-102. http://geodesic.mathdoc.fr/item/DA_2006_13_3_a5/

[1] Vinokurov S. F., Peryazev N. A. (red.), Izbrannye voprosy teorii bulevykh funktsii, Fizmatlit, M., 2001 | Zbl

[2] Panteleev V. I., “Polinomialnye razlozheniya $k$-znachnykh funktsii po nevyrozhdennym funktsiyam”, Matematicheskie zametki, 55:1 (1994), 144–149 | MR | Zbl

[3] Peryazev N. A., “Slozhnost bulevykh funktsii v klasse polinomialnykh polyarizovannykh form”, Algebra i logika, 34:3 (1995), 323–326 | MR | Zbl

[4] Selezneva S. N., “O slozhnosti predstavleniya funktsii mnogoznachnykh logik polyarizovannymi polinomami”, Diskretnaya matematika, 14:2 (2002), 48–53 | MR | Zbl

[5] Selezneva S. N., “O slozhnosti polyarizovannykh polinomov funktsii mnogoznachnykh logik, zavisyaschikh ot odnoi peremennoi”, Diskretnaya matematika, 16:2 (2004), 117–120 | MR | Zbl