O(logm)-approximation for the routing open shop problem
Kononov, Alexander1, 2
1 Sobolev Institute of Mathematics, Russia.
2 Novosibirsk State University, Russia
RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 383-391.

We consider the routing open shop problem which is a generalization of the open shop and the metric travelling salesman problems. The jobs are located in some transportation network, and the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all jobs. The goal is to find a non-preemptive schedule with the minimum makespan. We present a new polynomial-time approximation algorithm with worst-case performance guarantee O(logm), where m is the number of machines.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014051
Classification : 90B06, 90B35, 68W25
Mots-clés : Open shop, routing, approximation algorithms
Kononov, Alexander 1, 2

1 Sobolev Institute of Mathematics, Russia.
2 Novosibirsk State University, Russia 
@article{RO_2015__49_2_383_0,
     author = {Kononov, Alexander},
     editor = {Blazewicz, Jacek and Pesch, Erwin and Philipps, Cynthia and Trystram, Denis and Zhang, Guochuan},
     title = {$O(log\hspace{0.167em}m)$-approximation for the routing open shop problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {383--391},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {2},
     year = {2015},
     doi = {10.1051/ro/2014051},
     zbl = {1310.90014},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2014051/}
}
TY  - JOUR
AU  - Kononov, Alexander
ED  - Blazewicz, Jacek
ED  - Pesch, Erwin
ED  - Philipps, Cynthia
ED  - Trystram, Denis
ED  - Zhang, Guochuan
TI  - $O(log\hspace{0.167em}m)$-approximation for the routing open shop problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 383
EP  - 391
VL  - 49
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2014051/
DO  - 10.1051/ro/2014051
LA  - en
ID  - RO_2015__49_2_383_0
ER  - 
%0 Journal Article
%A Kononov, Alexander
%E Blazewicz, Jacek
%E Pesch, Erwin
%E Philipps, Cynthia
%E Trystram, Denis
%E Zhang, Guochuan
%T $O(log\hspace{0.167em}m)$-approximation for the routing open shop problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 383-391
%V 49
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2014051/
%R 10.1051/ro/2014051
%G en
%F RO_2015__49_2_383_0
Kononov, Alexander. $O(log\hspace{0.167em}m)$-approximation for the routing open shop problem. RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 383-391. doi : 10.1051/ro/2014051. http://www.numdam.org/articles/10.1051/ro/2014051/

I. Averbakh and O. Berman, A simple heuristic for m-machine flow-shop and its applications in routing-scheduling problems. Oper. Res. 47 (1999) 165–170. | DOI | Zbl

I. Averbakh, O. Berman and I. Chernykh, A 6 5-approximation algorithm for the two-machine routing open shop problem on a 2-node network. Eur. J. Oper. Res. 166 (2005) 3–24. | DOI | Zbl

I. Averbakh, O. Berman and I. Chernykh, The routing open-shop problem on a network: complexity and approximation. Eur. J. Oper. Res. 173 (2006) 521–539. | DOI | Zbl

K. Chandrasekaran, N. Goyal and B. Haeupler, Deterministic algorithms for the Lovasz local lemma, in the Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (2010) 992–1004. | Zbl

I. Chernykh, N. Dryuck, A. Kononov and S. Sevastyanov, The routing open-shop problem: New approximation algorithms, in the Proceedings of WAOA, edited by E. Bampis, K. Jansen 2009, in Vol. 5893 of Lect. Notes Comput. Sci. (2010) 75–85. | Zbl

I. Chernykh, A. Kononov and S. Sevastyanov, Efficient approximation algorithms for the routing open shop problem. Comput. Oper. Res. 40 (2013) 841–847. | DOI | Zbl

N. Christofides, Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, Report 388. Graduate School of Industrial Administration. Carnegie-Mellon University, Pittsburgh, PA (1976).

M. Garey and D. Johnson, Computers and Intractability, A Guide to the theory of NP-completeness. W.H. Freemann and Company, San Francisco, CA (1979). | Zbl

T. Gonzalez and S. Sahni, Open Shop Scheduling to Minimize Finish Time. J. ACM 23 (1976) 665–679. | DOI | Zbl

A. Kononov, On the routing open shop problem with two machines on a two-vertex network. J. Appl. Ind. Math. 6 (2012) 318–331, Original Russian Text A.V. Kononov, published in Diskretnyi Analiz i Issledovanie Operatsii 19 (2012) 55–75. | DOI | Zbl

E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, Sequencing and scheduling: algorithms and complexity. Vol. 4 of Handbooks Oper. Res. Management Science, Logistics of Production and Inventory. North Holland, Amsterdam (1993) 445–522.

F.T. Leighton, B.M. Maggs and S.B. Rao, Packet routing and job-scheduling in O(congestion + dilation) steps. Combinatorica 14 (1994) 167–186. | DOI | Zbl

F.T. Leighton, B.M. Maggs and A.W. Richa, Fast algorithms for finding O(Congestion + Dilation) packet routing schedules. Combinatorica 19 (1999) 375–401. | DOI | Zbl

R.A. Moser and G. Tardos, A constructive proof of the general Lovasz Local Lemma. J. ACM 57 (2010) 11:1–11:15. | DOI | Zbl

B. Peis and A. Wiese, Universal Packet Routing with Arbitrary Bandwidth and Transit Times, in the Proc. of IPCO, 2011, edited by O. Günlük and G. Woeginger. Lect. Notes Comput. Sci. 6655 (2011) 362–375. | Zbl

A. Serdyukov, On some extremal routes in graphs. Upravlyaemye Sistemy 17 (1978) 76–79 (in Russian). | Zbl

D. Shmoys, C. Stein and J. Wein, Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. 23 (1994) 617–632. | DOI | Zbl

V. F. Yu, S.-W. Lin and S.-Y. Chou, The museum visitor routing problem. Appl. Math. Comput. 216 (2010) 719–729. | Zbl

W. Yu and G. Zhang, Improved approximation algorithms for routing shop scheduling, in the Proc. of ISAAC 2011. Lect. Notes Comput. Sci. 7074 (2011) 30–39. | Zbl

D.P. Williamson, L.A. Hall, J.A. Hoogeveen, C.A.J. Hurkens, J.K. Lenstra, S.V. Sevastianov and D.B. Shmoys, Short shop schedules. Oper. Res. 45 (1997) 288–294. | DOI | Zbl

Cité par Sources :