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.

Krzysztof Pastuszak, Michał Małafiejski, Krzysztof Ocetkiewicz. (2017). No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs, 65-72.

Informacje szczegółowe

Kategoria:
Inna publikacyjna praca zbiorowa (w tym materiały konferencyjne)
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: Agencja Reklamowo-Wydawnicza „Ostoja”, Cianowice, ul. Niebyła 17, 32-043 Skała , 2017, s.65-72

wyświetlono 40 razy

Publikacje, które mogą cię zainteresować

Meta Tagi