Zefektivnění výpočtu optimálních dávek vícestupňového výrobního procesu

A More Efficient Computation of Optimal Lot Sizes in a Multistage Production Process

článek v časopise - ostatní, Jost

čeština

Tato práce navazuje na naši práci [4], a pokud není uvedeno jinak, používá symbolů, které v ní byly definovány. Odkazy na vzorce práce [4] budou vyznačeny předřazením symbolu I. před vzorce; tak např. (I.12) značí vzorec (12) práce [4]. Zabýváme se zde problémem (I. 1)--(I. 9) minimalizace ovlivnitelných nákladů vícestupňového výrobního procesu se sériově uspořádanými stupni z hlediska možnosti dalšího zefektivnění algoritmu dynamického programování, jehož jsme použili k přesnému řešení. Toto zefektivnění lze provést redukcí množiny S_i (I. 8) rozhodovacích proměnných problému. Tato redukce může být buďto heuristická, nebo taková, která zaručuje, že optimální hodnota rozhodovací proměnné patří do množiny, která je výsledkem této redukce. Prvním z obou uvedených typů redukce se zabýváme v kapitolách 2--4. V kapitole 2 navrhujeme heuristickou metodu zlepšující redukci v [4]. V kapitole 3 odvozujeme dolní hranici optimálních nákladů, která je zlepšením dolní hranice odvozené v [3, 5, 6]. Modifikace stratégie, uplatněné při odvozování této dolní hranice, používáme k nalezení nové heuristické redukce množiny S_i. Výsledky jednotlivých heuristických metod jsou experimentálně vyhodnoceny v kapitole 4, kde jsou též srovnány naše přístupy s přístupy jiných autorů. V kapitole 5 se zabýváme druhým z uvedených typů redukce, který zaručuje, že získané řešení je řešením přesným. Z horních a dolních hranic optimálních nákladů vícestupňových výrobních procesů stanovujeme horní hranici složky aditivní kriteriální funkce. Vzhledem ke konvexnosti této funkce příslušnou redukci množiny S_i snadno nalezneme.

In [4] we suggested a heuristic way of the reduction of the set of feasible decisions in a dynamic programming problem of the choice of lot sizes to minimize costs in a multi-stage production process with stages arranged in a series. The present paper describes certain improvement of the heuristic process which in an overwhelming majority of the cases considered gives the amount of costs which is nearer to the exact solution. Up to now, our heuristic reductions were based on the strategy of the lower bound of optimal costs which was derived by dynamic programming (see [3], [5], [6]). In the present paper, that lower bound is improved by setting upper and lower limits for the lot size. The modification of the strategy used to derive the lower bound is applied for a new heuristic reduction of the set of feasible dcisions. In the considered sample of 137 production processes where the number of stages amounts to 26, the mean error of costs computed by the above methods does not exceed 0.5% of optimal costs. In approximately 99% of the proccesses from this sample the heuristic method leads to the exact solution. For some production processes, however, the heuristic method of [4] leads to better results. On the whole, the average reduction of computing time by 57,7% was reached by the heuristic approaches. In the paper, further, such reduction of the set of feasible decisions is proposed which guarantees that the resulting solution is the exact one. This reduction is based on setting upper and lower limits for the optimal costs of multistage production processes. The average reduction of computing time reached in this way was 26.7%. We consider here multistage production processes of more general type than other authors dealing with similar problems.

lot sizes, multistage production process

KLAPKA, J.; DVOŘÁK, J.

1. 1. 1980

ACADEMIA

Praha

0013-3027

Ekonomicko-matematický obzor

16

2

Česká republika

179

189

11