Restricted open shop scheduling

• Autorzy: Małafiejski M. , Pastuszak K.
• Języki publikacji: EN

Abstrakty

EN

In the real applications the open shop scheduling models often require some additional constraints and adequate models. We concern the restrictions in the open shop scheduling related to an instance of the problem and to a feasible solution. Precisely, we require that each jobs consists of the bounded number of operations and each machine has a bounded load (i.e., the total number of operations executed on this machine in a schedule). Moreover, in any feasible schedule we require some predetermined delays between the subsequent operations of the same job (no delays in the no-wait restriction) and each machine is working without any idle time ( no-idle restriction). Although the open shop scheduling problem is NP-hard in general, we show some polynomial time algorithms using chromatic scheduling models for the selected open shop scheduling problems.

Słowa kluczowe

EN

open shop scheduling; no-wait & no-idle schedules; scheduling bipartite graph; interval graph coloring

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Journal of Theoretical and Applied Computer Science
• Rocznik: 2017
• Tom: Vol. 11, nr 1
• Strony: 20--27
• Opis fizyczny: Bibliogr. 23 poz., tab.

Twórcy

autor

Małafiejski M.

• Department of Algorithms and Systems Modelling, Gdańsk University of Technology, Poland

autor

Pastuszak K.

• Department of Algorithms and Systems Modelling, Gdańsk University of Technology, Poland

Bibliografia

• [1] Gonzalez, T., Sahni, S.: Open shop scheduling to minimize finish time. Journal of the ACM, pp. 665–679, 1976.
• [2] Giaro, K.: Task scheduling by graph coloring (in Polish), D.Sc. Dissertation. Gdansk University of Technology, 2003.
• [3] Graham, R., Lawler, E., Lenstra, J., Rinnooy Kan, A.: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium., pp. 287–326, 1979.
• [4] Pinedo, M. L.: Scheduling: Theory, Algorithms, and Systems, Third Edition. Springer, 2008.
• [5] Zhang, Z.-H., Bai, D.: An extended study on an open-shop scheduling problem using the minimisation of the sum of quadratic completion times. Applied Mathematics and Computation, pp. 238–47, 2014.
• [6] Baptiste, P.: On minimizing the weighted number of late jobs in unit execution time open-shops. European Journal of Operational Research, pp. 344–354, 2003.
• [7] Naderi, Zandieh, M.: Modeling and scheduling no-wait open shop problems. International Journal of Production Economics, pp. 256–266, 2014.
• [8] Ciro, G. C., Dugardin, F., Yalaoui, F., Kelly, R.: A fuzzy ant colony optimization to solve an open shop scheduling problem with multi-skills resource constraints. IFAC-PapersOnLine, 15th IFAC Symposium onInformation Control Problems in Manufacturing — INCOM 2015, pp. 715–720, 2015.
• [9] Blum, C.: Beam-ACO-hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers & Operations Research, pp. 1565–1591, 2005.
• [10] Chinyao, L., Yuling, Y.: Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated. Robotics and Computer-Integrated Manufacturing, pp. 314–322, 2009.
• [11] Matta, M. E.: A genetic algorithm for the proportionate multiprocessor open shop. Computers Operations Research, pp. 2601–2618, 2009.
• [12] Małafiejska, A.: Incidence graph coloring (in Polish), Ph.D. Thesis. University of Gdansk, 2016.
• [13] Schrijver, A.: Bipartite edge-colouring in O(_m) time. SIAM Journal on Computing, pp. 841–846, 1999.
• [14] Cole, R., Oste, K., Schirra, S.: Edge-Coloring Bipartite Multigraphs in O(|E| log _). Combinatorica, p. 5–12, 2001.
• [15] Sahni, S., Cho, Y.: Complexity of Scheduling Shops with No Wait in Process. Mathematics of Operations Research, pp. 448–457, 1979.
• [16] Gonzalez, T.: Unit Execution Time Shop Problems. Mathematics of Operations Research, pp. 2601–2618, 1982.
• [17] Casselgren, C., Toft, B.: One-sided interval edge-colorings of bipartite graphs. Discrete Mathematics, pp. 2628–2639, 2016.
• [18] Kamalian, R. R.: On one-sided interval edge colorings of biregular bipartite graphs. Algebra and Discrete Mathematics, pp. 193–199, 2003.
• [19] Consecutive colorings of the edges of general graphs. Discrete Mathematics, pp. 131–143, 2001.
• [20] Casselgren, C. J., Toft, B.: On Interval Edge Colorings of Biregular Bipartite Graphs With Small Vertex Degrees. Journal of Graph Theory, pp. 83–97, 2015.
• [21] Hanson, D., Loten, C. O. M., Toft, B.: On interval coloring of biregular bipartite graphs. Ars Combinatoria, pp. 23–32, 1998.
• [22] Hanson, D., Loten, C. O. M.: A lower bound for Interval colouring biregular bipartite graphs. Bulletin of the ICA, pp. 69–74, 1996.
• [23] Hansen, H.: Skemalaegning med henblik pa minimering af ventetid, M.Sc. Thesis. University of Odense, 1993.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).