nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti

verfasst von : Ilya Chernykh, Olga Krivonogova

Erschienen in: Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The object of investigation is the routing open shop problem, in which a fleet of machines have to visit all the nodes of a given transportation network to perform operations on some jobs located at those nodes. Each machine has to visit each node, to process each job and to return back to the common initial location—the depot. Operations of each job can be processed in an arbitrary sequence, any machine may perform at most one operation at a time. The goal is to construct a feasible schedule to minimize the makespan. The routing open shop problem is known to be NP-hard even in the simplest two-machine case with the transportation network consisting of just two nodes (including the depot). We consider a certain generalization of this problem in which travel times are individual for each of the two machines and the structure of the transportation network is an arbitrary cactus. We generalize an instance reduction algorithm known for the problem on a tree with identical travel times, and use it to describe new polynomially solvable cases for the problem, as well as an efficient approximation algorithm for another special case with a tight approximation ratio guarantee.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Local Strong Convexity in Hilbert Space

Aksyonov, V.: An approximation polynomial time algorithm for one scheduling problem. Upravlyaemye systemy 28, 8–11 (1988). (in Russian)

Averbakh, I., Berman, O.: Routing two-machine flowshop problems on networks with special structure. Transp. Sci. 30(4), 303–314 (1996). https://doi.org/10.1287/trsc.30.4.303CrossRefMATH

Averbakh, I., Berman, O.: A simple heuristic for \(m\)-machine flow-shop and its applications in routing-scheduling problems. Oper. Res. 47(1), 165–170 (1999). https://doi.org/10.1287/opre.47.1.165CrossRefMATH

Averbakh, I., Berman, O., Chernykh, I.: A 6/5-approximation algorithm for the two-machine routing open-shop problem on a two-node network. Eur. J. Oper. Res. 166(1), 3–24 (2005). https://doi.org/10.1016/j.ejor.2003.06.050MathSciNetCrossRefMATH

Averbakh, I., Berman, O., Chernykh, I.: The routing open-shop problem on a network: complexity and approximation. Eur. J. Oper. Res. 173(2), 531–539 (2006). https://doi.org/10.1016/j.ejor.2005.01.034MathSciNetCrossRefMATH

Chernykh, I., Krivonogiva, O.: Optima localization for the two-machine routing open shop on a tree (2019). (in Russian), submitted to Diskretnyj Analiz i Issledovanie Operacij

Chernykh, I., Lgotina, E.: The 2-machine routing open shop on a triangular transportation network. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 284–297. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_23CrossRef

Chernykh, I., Lgotina, E.: How the difference in travel times affects the optima localization for the routing open shop. In: Khachay, M., Kochetov, Y., Pardalos, P. (eds.) MOTOR 2019. LNCS, vol. 11548, pp. 187–201. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22629-9_14CrossRef

Chernykh, I., Lgotina, E.: Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass (2019), submitted to Optimization Methods and Software

10.

Chernykh, I., Pyatkin, A.: Irreducible bin packing: complexity, solvability and application to the routing open shop. LNCS (2019, to appear)

11.

Chou, S., Lin, S.: Museum visitor routing problem with the ballancing of concurrent visitors. Complex Syst. Concurr. Eng. 6, 345–353 (2007). https://doi.org/10.1007/978-1-84628-976-7_39CrossRef

12.

Golovachev, M., Pyatkin, A.V.: Routing open shop with two nodes, unit processing times and equal number of jobs and machines. In: Khachay, M., Kochetov, Y., Pardalos, P. (eds.) MOTOR 2019. LNCS, vol. 11548, pp. 264–276. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22629-9_19CrossRef

13.

Gonzalez, T.F., Sahni, S.: Open shop scheduling to minimize finish time. J. ACM 23(4), 665–679 (1976). https://doi.org/10.1145/321978.321985MathSciNetCrossRefMATH

14.

Hopcroft, J., Tarjan, R.: Algorith 477: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973). https://doi.org/10.1145/362248.362272CrossRef

15.

Kononov, A., Sevastianov, S., Tchernykh, I.: When difference in machine loads leads to efficient scheduling in open shops. Ann. Oper. Res. 92, 211–239 (1999). https://doi.org/10.1023/a:1018986731638MathSciNetCrossRefMATH

16.

Kononov, A.: \(O(\log m)\)-approximation for the routing open shop problem. RAIRO-Oper. Res. 49, 383–391 (2015). https://doi.org/10.1051/ro/2014051MathSciNetCrossRefMATH

17.

Kononov, A.: On the routing open shop problem with two machines on a two-vertex network. J. Appl. Ind. Math. 6(3), 318–331 (2012). https://doi.org/10.1134/s1990478912030064MathSciNetCrossRefMATH

18.

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity, Chap. 9. In: Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, vol. 4, pp. 445–522. Elsevier (1993). https://doi.org/10.1016/S0927-0507(05)80189-6CrossRef

19.

Sevastianov, S.V., Woeginger, G.J.: Makespan minimization in open shops: a polynomial time approximation scheme. Math. Program. 82(1–2, Ser. B), 191–198 (1998). https://doi.org/10.1007/BF01585871MathSciNetCrossRef

20.

Sevastianov, S.V., Tchernykh, I.D.: Computer-aided way to prove theorems in scheduling. In: Bilardi, G., Italiano, G.F., Pietracaprina, A., Pucci, G. (eds.) ESA 1998. LNCS, vol. 1461, pp. 502–513. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-68530-8_42CrossRef

21.

Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972). https://doi.org/10.1137/0201010MathSciNetCrossRefMATH

22.

van Bevern, R., Pyatkin, A.V.: Completing partial schedules for open shop with unit processing times and routing. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 73–87. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-34171-2_6CrossRefMATH

23.

van Bevern, R., Pyatkin, A.V., Sevastyanov, S.V.: An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. Siberian Electron. Math. Rep. 16, 42–84 (2019). https://doi.org/10.33048/semi.2019.16.003MathSciNetCrossRefMATH

24.

Williamson, D.P., et al.: Short shop schedules. Oper. Res. 45(2), 288–294 (1997). https://doi.org/10.1287/opre.45.2.288MathSciNetCrossRefMATH

25.

Yu, V.F., Lin, S., Chou, S.: The museum visitor routing problem. Appl. Math. Comput. 216(3), 719–729 (2010). https://doi.org/10.1016/j.amc.2010.01.066CrossRefMATH

Titel: Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti
verfasst von: Ilya Chernykh
Olga Krivonogova
Verlag: Springer International Publishing
Buch: Optimization and Applications
Print ISBN: 978-3-030-38602-3

Electronic ISBN: 978-3-030-38603-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-38603-0_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"