No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs - Publikacja - MOST Wiedzy

Wyszukiwarka

No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs

Abstrakt

In the open shop scheduling with bioperational jobs each job consists of two unit operations with a delay between the end of the first operation and the beginning of the second one. No-wait requirement enforces that the delay between operations is equal to 0. No-idle means that there is no idle time on any machine. We model this problem by the interval incidentor (1, 1)-coloring (IIR(1, 1)-coloring) of a graph with the minimum number of colors which was introduced and researched extensively by Pyatkin and Vizing. An incidentor is a pair (v, e), where v is a vertex and e is an edge incident to v. In the incidentor coloring of a graph the colors of incidentors at the same vertex must differ. The interval incidentor (1, 1)-coloring is a restriction of the incidentor coloring by two additional requirements:colors at any vertex form an interval of integers and the colors of incidentors of the same edge differ exactly by one. In the paper we proposed the polynomial time algorithm solving the problem of IIR(1, 1)-coloring for graphs with degree bounded by 4, i.e., we solved the problem of minimum makespan open shop scheduling of bioperational jobs with no-wait & no-idle requirements with the restriction that each machine handles at most 4 job.

Cytuj jako

Pełna treść

pobierz publikację
pobrano 49 razy
Wersja publikacji
Accepted albo Published Version
Licencja
Copyright (AGH-UST, Kraków, Poland, 2017)

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Aktywność konferencyjna
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:
DMMS 2017 & ZTS XX Proceedings strony 65 - 72
Język:
angielski
Rok wydania:
2017
Opis bibliograficzny:
Pastuszak K., Małafiejski M., Ocetkiewicz K.: No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs// DMMS 2017 & ZTS XX Proceedings/ ed. Prof. Tadeusz Sawik, PhD, ScD AGH University of Science and Technology Faculty of Management Kraków: , 2017, s.65-72
Bibliografia: test
  1. Giaro, K. (2003). Task scheduling by graph coloring (in Polish). D.Sc. Dissertation. Gdansk University of Technology. otwiera się w nowej karcie
  2. Giaro, K. (1997). The complexity of consecutive D-coloring of bipartite graphs: 4 is easy, 5 is hard. Ars Combinatoria 47, pp. 287-300.
  3. Gonzalez, T., Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the ACM, pp. 665- 679. otwiera się w nowej karcie
  4. Graham, R., Lawler, E., Lenstra, J., Rinnooy Kan, A. (1979). 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. otwiera się w nowej karcie
  5. Hanson, D., Loten, C. O. M., Toft, B. (1998). On interval coloring of biregular bipartite graphs. Ars ombinatoria, pp. 23-32.
  6. Małafiejska, A. (2016). Wybrane problemy i modele końcówkowego kolorowania grafów (in Polish). Raport Tech. WETI 3/2016, Politechnika Gdańska (2016), pp. 1-19.
  7. Melynikov, L., Pyatkin, A., Vizing, V. (2000). On the (k, l)-coloring of incidentors (in Russian). Diskretn. Anal. Issled. Oper. 1, pp. 29-37.
  8. Pyatkin, A. V. (1997a). Some optimization problems of scheduling the transmission of messages in a local communication network. Operations Research and Discrete Analysis, pp. 227-232, 1997. otwiera się w nowej karcie
  9. Pyatkin, A. (1997b). The incidentor coloring problems and their applications, Ph.D. Dissertation (in Russian). Institute of Mathematics SB RAS, Novosibirsk. otwiera się w nowej karcie
  10. Pyatkin, A. V. (2002). The incidentor coloring of multigraphs and its applications. Electronic Notes in Discrete Mathematics, pp. 103-104.
  11. Pyatkin, A. (2004). Upper and lower bounds for an incidentor (k,l)-chromatic number (in Russian). Diskretn. Anal. Issled. Oper., 1, pp. 93-102.
  12. Pyatkin, A., Vizing, V. (2006). Incidentor coloring of weighted multigraphs. Discrete Applied Mathematics, 120, pp. 209-217.
  13. Pyatkin, A. (2013). Incidentor coloring: Methods and results. Graph Theory and Interactions, Durham. otwiera się w nowej karcie
  14. Pyatkin, A. (2015). On an Interval (1,1)-Coloring of Incidentors of Interval Colorable Graphs. Journal of Applied and Industrial Mathematics, 9, pp. 271-278. otwiera się w nowej karcie
  15. Vizing, V. (2000). On Incidentor Coloring in a Partially Directed Multigraph. Fuzzy Sets and Systems, pp. 141-147. otwiera się w nowej karcie
  16. Vizing, V. (2003). Interval colorings of the incidentors of an undirected multigraph (in Russian). Diskretn. Anal. Issled. Oper. pp. 14-40. otwiera się w nowej karcie
  17. Vizing, V. (2005). On the (p, q)-coloring of incidentors of an undirected multigraph (in Russian). Diskretn. Anal. Issled. Oper. 1, pp. 23-39. otwiera się w nowej karcie
  18. Vizing, V. (2007). On Bounds for the Incidentor Chromatic Number of a Directed Weighted Multigraph. Journal of Applied and Industrial Mathematics, 1, pp. 504-508. otwiera się w nowej karcie
  19. Vizing, V. (2009). On Incidentor Coloring in a Hypergraph. Journal of Applied and Industrial Mathematics, 3, pp. 144-147. otwiera się w nowej karcie
  20. Vizing, V. (2012). Multicoloring the Incidentors of a Weighted Undirected Multigraph. Journal of Applied and Industrial Mathematics, 6, pp. 514-521. otwiera się w nowej karcie
  21. Vizing, V. (2014). Multicoloring the Incidentors of a Weighted Directed Multigraph. Journal of Applied and Industrial Mathematics, 8, pp. 604-608. otwiera się w nowej karcie
Weryfikacja:
Politechnika Gdańska

wyświetlono 185 razy

Publikacje, które mogą cię zainteresować

Meta Tagi