$O(log\hspace{0.167em}m)$-approximation for the routing open shop problem

Kononov, Alexander

doi:10.1051/ro/2014051

O (l o g m)

-approximation for the routing open shop problem

Kononov, Alexander ^1,²

¹ Sobolev Institute of Mathematics, Russia.
² Novosibirsk State University, Russia

Blazewicz, Jacek ; Pesch, Erwin ; Philipps, Cynthia ; Trystram, Denis ; Zhang, Guochuan(éd.)

RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 383-391

Voir la notice de l'article provenant de la source Numdam

Résumé

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 (l o g m),$ where $m$ is the number of machines.

Reçu le : 2012-02-15
Accepté le : 2014-09-26

Zbl

DOI : 10.1051/ro/2014051

Classification : 90B06, 90B35, 68W25
Keywords: Open shop, routing, approximation algorithms

Affiliations des auteurs :

Kononov, Alexander ^{1, 2}

¹ Sobolev Institute of Mathematics, Russia.
² 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :

Parcourir par

Geodesic

Parcourir par