Sensitivity Analysis in Sequencing Problems

• Autorzy: Adam Kasperski

Warianty tytułu

Analiza wrażliwości w problemach kolejnościowych

• Języki publikacji: EN

Abstrakty

EN

In this paper, three particular sequencing problems are considered. It is shown how to perform the sensitivity analysis for each of these problems. The sensitivity analysis consists in checking how the values of given parameters can vary so that the obtained optimal sequence of jobs remains optimal.

Problem kolejnościowy jest specjalnym przypadkiem ogólniejszego problemu szeregowania. W problemie kolejnościowym celem podejmującego decyzję jest wyznaczenie dopuszczalnej kolejności (permutacji) prac, dla której wartość zadanej funkcji kosztu jest najmniejsza. W typowym problemie kolejnościowym zadane są pewne parametry (np. czas trwania prac), których wartości muszą być ustalone przed wyznaczeniem optymalnego rozwiązania. Po wyznaczeniu optymalnej kolejności prac istotne może być pytanie o stabilność otrzymanego rozwiązania. Można zapytać, w jakim zakresie mogą się zmieniać wartości parametrów problemu, aby otrzymane rozwiązanie pozostało optymalne? Taka analiza nazywana jest analizą wrażliwości. Aby otrzymać efektywną metodę przeprowadzenia analizy wrażliwości, każdy szczególny przypadek problemu kolejnościowego należy badać osobno. W artykule przedstawiono efektywne metody przeprowadzenia analizy wrażliwości dla trzech wybranych problemów kolejnościowych.

Słowa kluczowe

EN

Operations research; Optimizing models; Task scheduling theory

PL

Badania operacyjne; Modele optymalizacyjne; Teoria szeregowania zadań

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2003
• Numer: nr 4
• Strony: 85--96

Twórcy

autor

Adam Kasperski

Bibliografia

• [1] ADOLPHSON A, HU T.C., Optimal Linear Ordering, SIAM Journal of Applied Mathematics, 25(3) (1973), 403-423.
• [2] BRUCKER P., Scheduling Algorithms, Second Revised and Enlarged Edition, 1998.
• [3] CHANAS S., KASPERSKI A., Sufficient and necessary condition of optimality in the single machine scheduling problem with weighted sum of completion times, Technical Reports of Institute of Ind.Eng. and Mngmt., PRE 21 (2002).
• [4] CHANAS S., KASPERSKI A., Sensitivity analysis in the single machine scheduling problem with max-min criterion, submitted to International Transaction in Operational Research.
• [5] CHANAS S., KASPERSKI A., Possible and necessary optimality of solutions it the single machine scheduling problem with fuzzy parameters, to appear in Fuzzy Sets and Systems.
• [6] LIN Y., DENG J., On the structure of all optimal solutions of the two-machine flow shop scheduling problem, OR Transactions, 3(2) (1999), 10-20.
• [7] JOHNSON S.M., Optimal two and three stage production schedule with setup times included, Naval res. Logis. Quart., 1 (1954), 61-68.
• [8] LAWLER E.L., Optimal sequencing of a single machine subject to precedence constraints, Management Science, 19 (1973), 544-546.
• [9] SOTSKOV Yu.N., LEONTEV V.K., GORDEEV E.N., Some concepts of stability analysis in combinatorial optimization, Discrete Applied Mathematics, 58 (1995), 169-190).