Wielomaszynowy problem szeregowania z optymalizowanymi przedziałami czasowymi zakończenia wykonywania zadań

• Autorzy: Janiak, A. , Marek, M.

Warianty tytułu

DE

Optimal assignment of due intervals in single machine scheduling problems

• Języki publikacji: PL

Abstrakty

PL

W pracy rozpatrywany jest wielomaszynowy problem szeregowania, w którym dla zadań dobierane są optymalnie przedziały czasowe zakończenia ich wykonywania. Rozpatrywany przypadek jest uogólnieniem znanych z literatury naukowej problemów, w których dokonywano doboru pożądanych terminów zakończenia wykonania zadań. Dla badanego w pracy problemu należy znaleźć takie uszeregowanie zadań na identycznych maszynach równoległych oraz takie wartości parametrów określających położenie optymalizowanych przedziałów na osi czasu, które minimalizują rozpatrywane kryterium. W kryterium tym, karze podlegają zarówno zadania wykonane zbyt wcześnie (odpowiada to kosztom przechowywania produktu gotowego), jak również zadania spóźnione (odpowiada to kosztom nie dotrzymania terminu realizacji). Dodatkowo, kryterium to, zależy także od wartości parametrów określających jakość dobieranych przedziałów czasowych. Wykazano NP-zupełność badanego problemu, wykorzystując do tego NP-zupełny Problem Podziału.

EN

The paper deals with single machine scheduling problems, in which a due interval should be assigned to each job. Due interval is a generalization of well known classical due date and describes a time interval, in which a job should be finished. Due interval assignment is completely new approach and to our knowledge has not been investigated in the scientific literature. We consider two single machine scheduling problems, in which different models of due intervals are introduced. The problem is to find a sequence of jobs and an assignment of due intervals to each job, which minimize the maximum of the following three parts: the maximum tardiness, the maximum earliness and the due interval parameters. Based on proved properties, we constructed the optimal solutions for both problems under considerations.

Słowa kluczowe

PL

szeregowanie zadań

EN

scheduling

• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2001
• Tom: T. 5, z. 1/2
• Strony: 277-281
• Opis fizyczny: Bibliogr. 6 poz., rys.

Twórcy

autor

Janiak, A.

autor

Marek, M.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska

Bibliografia

• [1] Baker K.R., Scudder G.D.: Sequencing with earliness and tardiness penalties: a review. Operations Research, vol. 30, 1990, 22-36
• [2] Chen Z.L., Cheng T.C.E.: Parallel-machine scheduling problem with earliness and tardiness penalties. Journal of the Operational Research Society, vol. 45/6,1994, 685-695
• [3] Cheng T.C.E., Gupta M.C.: Survey of scheduling research involving due date determination decision. European Journal of Operational Research, vol. 38, 1989,156-166
• [4] Garey M.R., Johnson D.S.: Computers and intractability: a guide to the theory of NP-completeness. San Francisco, W.H. Freeman 1979
• [5] Graham R.L., Lawler E.L., Lanstra J.K., Rinnoy Kan A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math., vol. 5,1979,287-326
• [6] Janiak A., Marek M.: Jednomaszynowy problem szeregowania z optymalizowanymi przedziałami czasowymi zakończenia wykonywania zadań. Zesz. Nauk. Polit. ŚL, Seria Automatyka, 129, 2000, 145-155