Domino sequencing: scheduling with state-based sequence-dependent setup times. (English) Zbl 1476.90114
Summary: We introduce the Domino Sequencing problem, a scheduling problem with special sequence-dependent setup times. For each job \(j\), there are corresponding start and end states \(a_j\) and \(b_j\). When job \(j\) is scheduled immediately before job \(k\), a setup time of 1 is needed if \(b_j \neq a_k\). We present polynomial-time algorithms for various versions. When jobs are partitioned into families, we show that the problem becomes \(\mathsf{NP}\)-hard and present a fixed-parameter tractable algorithm.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
sequence-dependent setup times; job families; Eulerian extension problem; dynamic programming; fixed-parameter tractabilityReferences:
| [1] | Allahverdi, A., The third comprehensive survey on scheduling problems with setup times/costs, European J. Oper. Res., 246, 2, 345-378 (2015) · Zbl 1347.90031 |
| [2] | Allahverdi, A.; Gupta, J. N.; Aldowaisan, T., A review of scheduling research involving setup considerations, Omega, 27, 2, 219-239 (1999) |
| [3] | Allahverdi, A.; Ng, C.; Cheng, T.; Kovalyov, M. Y., A survey of scheduling problems with setup times or costs, European J. Oper. Res., 187, 3, 985-1032 (2008) · Zbl 1137.90474 |
| [4] | Allahverdi, A.; Soroush, H., The significance of reducing setup times/setup costs, European J. Oper. Res., 187, 3, 978-984 (2008) · Zbl 1137.90475 |
| [5] | Bellman, R., Dynamic programming treatment of the travelling salesman problem, J. ACM, 9, 1, 61-63 (1962) · Zbl 0106.14102 |
| [6] | Berger, A.; Kozma, L.; Mnich, M.; Vincze, R., A time- and space-optimal algorithm for the many-visits TSP, (Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (2019)) · Zbl 1432.68614 |
| [7] | Billaut, J.-C.; Della Croce, F.; Salassa, F.; T’kindt, V., No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and hamiltonian paths, J. Sched., 22, 59-68 (2019) · Zbl 1425.90040 |
| [8] | Boesch, F. T.; Suffel, C.; Tindell, R., The spanning subgraphs of eulerian graphs, J. Graph Theory, 1, 1, 79-84 (1977) · Zbl 0363.05042 |
| [9] | Demaine, E. D.; Ma, F.; Waingarten, E., Playing dominoes is hard, except by yourself, (Ferro, A.; Luccio, F.; Widmayer, P., Fun with Algorithms (2014), Springer International Publishing: Springer International Publishing Cham), 137-146 |
| [10] | Diessel, E., Design and Analysis of Algorithms for Packing and Sequencing in the Production of Glued Laminated Timber (2018), Technische Universität Kaiserslautern, Technische Universität Kaiserslautern, (B.Sc. Thesis) |
| [11] | Dorn, F.; Moser, H.; Niedermeier, R.; Weller, M., Efficient algorithms for Eulerian extension and rural postman, SIAM J. Discrete Math., 27, 1, 75-94 (2013) · Zbl 1267.05131 |
| [12] | Eiselt, H. A.; Gendreau, M.; Laporte, G., Arc routing problems, part II: The rural postman problem, Oper. Res., 43, 3, 399-414 (1995) · Zbl 0853.90042 |
| [13] | Garey, M. R.; Johnson, D. S.; Tarjan, R. E., The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 4, 704-714 (1976) · Zbl 0346.05110 |
| [14] | Gilmore, P. C.; Gomory, R. E., Sequencing a one state-variable machine: A solvable case of the traveling salesman problem, Oper. Res., 12, 5, 655-679 (1964) · Zbl 0126.36006 |
| [15] | Graham, R.; Lawler, E.; Lenstra, J.; Kan, A., Optimization and approximation in deterministic sequencing and scheduling: A survey, (Hammer, P.; Johnson, E.; Korte, B., Discrete Optimization II. Discrete Optimization II, Annals of Discrete Mathematics, vol. 5 (1979), Elsevier), 287-326 · Zbl 0411.90044 |
| [16] | Held, M.; Karp, R. M., A dynamic programming approach to sequencing problems, J. Soc. Ind. Appl. Math., 10, 1, 196-210 (1962) · Zbl 0106.14103 |
| [17] | Höhn, W.; Jacobs, T.; Megow, N., On eulerian extensions and their application to no-wait flowshop scheduling, J. Sched., 15, 3, 295-309 (2012) · Zbl 1280.90050 |
| [18] | Impagliazzo, R.; Paturi, R., On the complexity of k-SAT, J. Comput. System Sci., 62, 2, 367-375 (2001) · Zbl 0990.68079 |
| [19] | Mnich, M.; van Bevern, R., Parameterized complexity of machine scheduling: 15 open problems, Comput. Oper. Res., 100, 254-261 (2018) · Zbl 1458.90333 |
| [20] | Niedermeier, R., Ubiquitous parameterization – invitation to fixed-parameter algorithms, (Fiala, J.; Koubek, V.; Kratochvíl, J., Mathematical Foundations of Computer Science 2004 (2004), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 84-103 · Zbl 1096.68068 |
| [21] | Papadimitriou, C. H., On the complexity of edge traversing, J. ACM, 23, 3, 544-554 (1976) · Zbl 0351.90079 |
| [22] | Pinedo, M. L., Scheduling: Theory, Algorithms, and Systems (2012), Springer-Verlag New York · Zbl 1239.90002 |
| [23] | Plesńik, J., The NP-completeness of the Hamiltonian cycle problem in planar diagraphs with degree bound two, Inf. Process. Lett., 8, 4, 199-201 (1979) · Zbl 0399.68070 |
| [24] | van der Veen, J. A.; Zhang, S., Low-complexity algorithms for sequencing jobs with a fixed number of job-classes, Comput. Oper. Res., 23, 11, 1059-1067 (1996) · Zbl 0870.90073 |
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.
