×

An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times. (English) Zbl 1411.90161

Summary: For the Routing Open Shop problem with unit execution times, the first algorithm with parameterized complexity is designed for constructing an optimal schedule. Its running time is bounded by a function \((\mathrm{Pol}(|V|) + f (m, g)) \cdot |I|\), where \(\mathrm{Pol}(|V|)\) is a polynomial of the number of network nodes, \(f(m, g)\) is a function of the number of machines and the number of job locations, and \(|I|\) is the input length in its compact encoding.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Allahverdi, C. Ng, T.C.E. Cheng, M.Y. Kovalyov,A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187:3 (2008), 985-1032; doi: 10.1016/j.ejor.2006.06.060 MR2378326 · Zbl 1137.90474
[2] R. van Bevern, A.V. Pyatkin,Completing partial schedules for Open Shop with unit processing times and routing, In: Proceedings of the 11th International Computer Science Symposium in Russia (CSR’16), Springer, Lecture Notes · Zbl 1475.90025
[3] R. van Bevern, R. Niedermeier, M. Sorge, M. Weller,The complexity of arc routing problems, In: A. Corberan and G. Laporte (eds.)Arc Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization,20 (2014), SIAM-MOS, 19-52; doi: 10.1137/1.9781611973679.ch2 · Zbl 1377.90114
[4] R. van Bevern, C. Komusiewicz, M. Sorge,A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments, Networks,70:3 (2017), 262-278; doi: 10.1002/net.21742; MR3702528 · Zbl 1432.90024
[5] H.J. B¨ockenhauer, J. Hromkoviˇc, J. Kneis, J. Kupke,The parameterized approximability of TSP with deadlines, Theory of Computing Systems,41:3 (2007), 431-444; doi: 10.1007/s00224-007-1347-x; MR2352540 · Zbl 1148.68052
[6] R. Cole, K. Ost, S. Schirra,Edge-coloring bipartite multigraphs inO(ElogD) time,Combinatorica,21:1(2001),5-12;doi:10.1007/s004930170002; MR1805711 · Zbl 1107.05305
[7] M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh,Parameterized Algorithms, Springer, 2015; doi: 10.1007/978-3-319-21275-3; MR3380745 · Zbl 1334.90001
[8] A.Frank,E.Tardos,Anapplicationofsimultaneousdiophantine approximation in combinatorial optimization, Combinatorica,7:1 (1987), 49-65; doi: 10.1007/BF02579200; MR0905151 · Zbl 0641.90067
[9] T. Gonzalez, S. Sahni,Open shop scheduling to minimize finish time, Journal of the ACM,23:4 (1976), 665-679; doi: 10.1145/321978.321985; MR0429089 · Zbl 0343.68031
[10] G. Gutin, M. Jones, M. Wahlstr¨om,The mixed chinese postman problem parameterized by pathwidth and treedepth, SIAM Journal on Discrete Mathematics,30:4 (2016), 2177-2205; doi: 10.1137/15M1034337; MR3576563 · Zbl 1351.05100
[11] G. Gutin, M. Jones, B. Sheng,Parameterized complexity of thek-arc chinese postman problem, Journal of Computer and System Sciences,84(2017), 107- 119; doi: 10.1016/j.jcss.2016.07.006; MR3570171 · Zbl 1353.68132
[12] G. Gutin, M. Wahlstr¨om, A. Yeo,Rural Postman parameterized by the number of components of required edges, Journal of Computer and System Sciences, 83:1 (2017), 121-131; doi: 10.1016/j.jcss.2016.06.001; MR3546865 · Zbl 1350.68144
[13] P.N. Klein, D. Marx,A subexponential parameterized algorithm for Subset TSP on planar graphs, In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14), Society for Industrial and Applied Mathematics, (2014), 1812-1830; doi: 10.1137/1.9781611973402.131; MR3376491 · Zbl 1423.68214
[14] E. Lawler, J. Lenstra, A. Rinnooy Kan, D. Shmoys,Sequencing and scheduling: algorithms and complexity, In: Handbooks in operations research and management science, Logistics of production and inventory,4, North Holland, Amsterdam, (1993), 445-522; doi: 10.1016/S0927-0507(05)80189-6
[15] D. Lokshtanov,New methods in parameterized algorithms and complexity, PhD thesis, University of Bergen, Norway, (2009).
[16] M. Mnich, R. van Bevern,Parameterized complexity of machine scheduling: 15 open problems, Computers and Operations Research, (2018), in press; doi: 10.1016/j.cor.2018.07.020 · Zbl 1458.90333
[17] C.H. Papadimitriou, K. Steiglitz,Combinatorial optimization: algorithms and complexity, Dover Publications, Inc., Mineola. New York, (1998). MR1637890 · Zbl 0944.90066
[18] D. Williamson, L. Hall, J. Hoogeveen, C. Hurkens, J. Lenstra, S. Sevast’janov, D. Shmoys,Short shop schedules, Operations Research,45:2 (1997), 288-294; doi: 10.1287/opre.45.2.288; MR1644998 · Zbl 0890.90112
[19] X. Zhu, W.E. Wilhelm,Scheduling and lot sizing with sequence-dependent setup: A literature review, IIE Transactions,38:11 (2006), 987-1007; doi: 10
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.