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

• Autorzy: Nadolski A.

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.

Słowa kluczowe

PL

szeregowanie zadań; system przepływowy; system cylindryczny; algorytm wielomianowy; problem dwumaszynowy; problem NP-trudny

EN

scheduling; cylindrical flow shop; polynomial time algorithm; two machine problem; NP-hard

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 143
• Strony: 99--105
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Nadolski A.

• Katedra Algorytmów i Modelowania Systemów Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: [phone],

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.