PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym

Autorzy
Identyfikatory
Warianty tytułu
EN
Computational complexity of the problem of scheduling in cylindrical flow shop
Konferencja
XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
Języki publikacji
PL
Abstrakty
PL
W pracy rozważamy złożoność obliczeniową szeregowania zadań w cylindrycznym systemie przepływowym. Konstruujemy algorytm wielomianowy dla problemu dwumaszynowego oraz wykazujemy, że problem staje się NP-trudny przy szeregowaniu na trzech maszynach oraz na dwóch maszynach przy wymuszeniu braku obustronnych przestojów.
EN
We consider the scheduling problem in a cylindrical flow shop to minimize the cycle time. We provide a polynomial time algorithm in the case of two processors and prove that the problem becomes NP-hard in the case of three processors. Moreover, we show that scheduling with no-wait and no-idle constraints is NP-hard in the case of two processors.
Rocznik
Tom
Strony
99--105
Opis fizyczny
Bibliogr. 8 poz.
Twórcy
autor
  • Katedra Algorytmów i Modelowania Systemów Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: (058) 347-19-56, nadolski@eti.pg.gda.pl
Bibliografia
  • 1. Giaro K.: NP-hardness of compact scheduling in simplified open and flow shops. Europ. J. Oper. Res., 130, 2001, p. 90-98.
  • 2. Gonzalez T., Sahni S.: Open shop scheduling to minimize finish time. J. ACM, 3, 1976, p. 665-679.
  • 3. Hall N.G., Lee T.E., Posner M.E.: The complexity of cyclic shop scheduling problems. J. Scheduling, 5, 2002, p. 307-327.
  • 4. Johnson S.M.: Optimal two- and three-stage production schedules. Naval Res. Logist. Quart., 1, 1954, p. 61-68.
  • 5. Kubale M., Nadolski A.: Chromatic scheduling in cyclic open shop. Europ. J. Oper. Res., 164, 2005, p. 585-591.
  • 6. Lee T.E., Posner M.E.: Performance measures and schedule patterns in periodic job shops. Oper. Res., 45, 1997, p. 72-91.
  • 7. McCormick S.T., Pinedo M.L., Shenker S., Wolf B.: Sequencing in an Assembly Line with Blocking to Minimize Cycle Time. Oper. Res., 37, 1989, p. 925-935.
  • 8. Nadolski A.: Chromatyczne szeregowanie w cyklicznych systemach produkcyjnych. 2005. Rozprawa doktorska, Politechnika Gdańska.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL2-0012-0036
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.