WWW.DISSERS.RU


...
    !

Pages:     | 1 |   ...   | 67 | 68 || 70 | 71 |   ...   | 82 |

jm jm jm L For the job-shop problem J 2 | t t tU | Cmax the number of instances, solvable due to Theorem 2 may jm jm jm L be close to that for the flow-shop problem F 2 | t t tU | Cmax since there exists a main machine that jm jm jm defines the makespan, for the job-shop problem, and we have to test condition of Theorem 1 only for jobs of set J12 (or for jobs of set J21, respectively) Table 1. Percentage of instances solvable due to Theorem 1 with the processing times L uniformly distributed in the range [1,1000], and with tU = t + L.

jm jm L n 5 10 15 20 25 30 35 40 45 50 55 60 65 70 80 90 1 99.2 95.2 91.2 86.1 79.2 72.8 63.9 58.1 49.2 41.9 34.2 29.5 24 17.5 10.1 6.5 3.2 97.2 89.8 77.6 63.6 51 39.6 28.2 16.4 13.3 7.8 3.3 2.9 0.9 0.4 0.1 0 0.3 95 80.9 66.4 47.6 32.8 20.6 9.4 6.2 3.2 1.6 0.5 0.1 0 0 0 0 4 91.8 78.6 56 39.2 20.3 10.7 4.5 2.1 0.6 0.2 0 0 0 0 0 0 5 91 69.4 44.9 28.9 14.6 6 2 0.4 0.2 0 0 0 0 0 0 0 6 89.1 65 42.2 22.1 8.2 2.7 0.4 0.4 0.1 0.1 0 0 0 0 0 0 7 87.6 61 33.7 13.4 4.6 1.2 0.4 0.1 0 0 0 0 0 0 0 0 8 86.8 54.2 27.3 12.7 3.2 0.9 0.2 0 0 0 0 0 0 0 0 0 9 86.9 48.3 24.7 7.2 1.9 0.2 0 0 0 0 0 0 0 0 0 0 10 84.8 50.3 19 5.5 2 0.5 0.1 0 0 0 0 0 0 0 0 0 Table 2. Percentage of instances solvable due to Theorem 1 with the processing times L uniformly distributed in the range [1,10000], and with tU = t + L.

jm jm L n 5 10 15 20 25 30 35 40 45 50 55 60 65 70 80 90 1 100 99.6 99.6 98.6 97.6 96.8 96.2 94 94.3 90.4 88.9 87.6 86.4 84.8 80.2 75.1 71.2 99.7 98.9 97.6 95.2 93.6 92.7 86.8 85.3 82.9 76.4 73.2 71.1 63 59.4 50 44.5 3 99.9 97.4 95.2 93.7 90.2 86 82.6 73.5 69 64.2 58.5 55.8 46.3 42.5 34.3 25.2 17.4 98.9 97.6 93 89.2 83.2 81.5 74.7 67.9 62.7 52.8 49.3 42.6 39.5 31.8 22.3 14.8 9.5 99.4 95.9 92.9 87.1 80.1 77.2 68.6 60.8 53.1 45.1 40.8 31.6 27 20.2 14.7 7.8 4.6 98.7 96.2 91.9 85.9 79.9 70.8 61.4 54.9 49.1 38.7 32.9 24.9 20.6 15.5 9 4.6 3.7 99.2 95.4 89 82.9 72.5 67.7 56.2 49.5 41.2 32.5 25.7 19.7 14.2 12.6 5.6 3.1 0.8 98.1 93.6 87.6 79.7 68.2 62.2 53.8 44.3 35.9 24.4 20.8 16 12.1 6.6 3.6 1.2 0.9 98 93.5 86.1 76.4 68.4 58.4 48.1 41.8 28.9 23.1 17.4 12 7 5.5 2.5 0.6 0.10 98.2 95.2 86.5 76.5 66 52.4 45.7 34.8 27 17.9 12.6 8.7 6.6 3.9 1.9 0.1 296 Intelligent Systems Table 3. Percentage of instances solvable due to Theorem 1 with the processing times L uniformly distributed in the range [1,1000] and with tU = t (1 + L% /100%) jm jm L n 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 1 94.5 85.1 70 53.5 36.9 24.9 14.7 8.2 4.8 1.9 1.3 0.6 0.3 0 0 0 0 0 0 2 91.2 69.3 45.6 24.2 11.8 4.2 1.1 0.6 0.1 0 0 0 0 0 0 0 0 0 0 3 87.7 58.4 28.3 10.3 3.8 1.3 0.2 0 0 0 0 0 0 0 0 0 0 0 0 4 82.4 47.4 18.8 5.5 0.8 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 5 75.5 37.4 11.3 2.2 0.2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 72.5 32.4 7.8 1.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 66.9 25 5.4 0.7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 65.8 19.9 2.1 0.4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 63.4 18 2.4 0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 59.2 14.4 2 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Table 4. Percentage of instances solvable due to Theorem 1 with the processing times L uniformly distributed in the range [1,10000] and with tU = t (1 + L% /100%).

jm jm L n 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 1 94.5 81.5 63.4 45.9 28.9 18.9 11.3 5.3 3.2 1 0.4 0.3 0 0 0 0 0 0 0 2 89 69.2 39.3 22.5 10.1 4.1 1.2 0.4 0 0 0 0 0 0 0 0 0 0 0 3 84.3 55.8 26.9 9.7 2.3 0.4 0 0 0 0 0 0 0 0 0 0 0 0 0 4 80.2 44.6 17.5 4.4 1.2 0 0.2 0 0 0 0 0 0 0 0 0 0 0 0 5 76.1 35.2 10.4 2.2 0.2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 70.3 30.4 6.8 0.8 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 71 24.6 6.3 0.9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 63.6 20.6 3.4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 61.6 18.5 1.9 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 59.9 12.4 0.8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Conclusion and Acknowledgments It is clear that in spite of uncertainty of the job processing times it is necessary to choose only one schedule for the practical realization of the process. Theorem 1 allows obtain (without fail) a dominant permutation before realization of the process. Indeed, such a dominant schedule (if any) is the best one for any feasible realization of the job processing times.

Clearly, this approach is useful if the level of uncertainty is low enough (and the best results were obtained for the case considered in Table 2). If uncertainty exceeds a certain threshold, then others approaches outperform the approach based on Theorem 1. If there is no possibility to construct a dominant schedule, it may be fruitful to construct more general schedule form on the basis of partial job order. One can also consider the realization stage of a flow-shop scheduling, when a part of the schedule is already realized. It is interesting to know how to use additional information about realized operations in order to obtain better solution than that constructed before scheduling. It is also interesting to find sufficient conditions for choosing the unique permutation that is optimal for any feasible processing times of the remaining operations. In such a case, a realistic solution process can be seen as consisting of static and dynamic phases. At the static phase, a scheduler can construct a family of the dominant permutations. At the dynamic phase of the decision-making, a scheduler has to select an appropriate schedule from such a family of the dominant permutations to react in real-time to the actual processing times of the already completed jobs. If a scheduler cannot make right decision at time point > 0, he (she) has to use one of the solution policies, which does not guarantee to find an optimal schedule for any realization of the remaining job processing times. The solution policy may be optimistic or pessimistic (see [Aytud et al., 2005]), or a scheduler can minimize objective function in average.

XII-th International Conference "Knowledge - Dialogue - Solution" Some results of such investigations are given in paper [Ng et al., 2006], where it is illustrated how to use a family of the dominant permutations during practical realization of the process when side information about processing times of the jobs that already completed becomes available for a decision-maker. Such an approach falls into the category of predictive-reactive scheduling. The static phase may be considered as predictive scheduling and dynamic phase as reactive scheduling (see [Aytud et al., 2005; Gupta, Stafford, 2006]).

For an uncertain problem it may be necessary to look for an optimal scheduling policy that stochastically minimizes the makespan [Ku, Niu, 1986; Pinedo, 1995]. To this end, it is necessary to obtain the reliable probability distributions for the random processing times. In general case, the choice of the job may also be based on minimization of possible loss of the objective function value.

Acknowledgements The research was partially supported by INTAS (project 03-51-5501) and ISTC (project B-986). The authors would like to thank Ms. Natalia Egorova for help in computational experiments.

Bibliography [Aytug et al., 2005] H. Aytug, M.A. Lawley, K. McKay, S. Mohan, and R. Uzsoy. Executing production schedules in the face of uncertainties: A review and some future directions. European Journal of Operational Research. 161, 86-110, 2005.

[Davenport, Beck, 2000] A.J. Davenport, and J.C. Beck A survey for techniques for scheduling with uncertainty. Unpublished, available from http://www.eil.toronto.ca/profiles/chris/chris.papers.html, 2000.

[Elmaghraby, Thoney, 2000] S. Elmaghraby, and K.A. Thoney. Two-machine flowshop problem with arbitrary processing time distributions. IIE Transactions, 31, 467-477, 2000.

[Gupta, Stafford, 2006] J.N.D. Gupta, and E.F. Stafford Jr. Flowshop scheduling research after five decades. European Journal of Operational Research. 169, 699-711, 2006.

[Jackson, 1956] J.R. Jackson. An extension of Johnson's results on job lot scheduling. Naval Res. Logist. Quart., 3, 201-203, 1956.

[Jansen, Mastrolilli, Solis-Oba, 2005] K. Jansen, M. Mastrolilli, R. Solis-Oba. Approximation schemes for job shop scheduling problems with controllable processing times. European Journal of Operational Research. 167, 297-319, 2005.

[Johnson, 1954] S.M. Johnson. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 6168, 1954.

[Ku, Niu, 1986] P.S. Ku, and S.C. Niu. On Johnson's two-machine flow-shop with random processing times. Operations Research. 34, 130-136, 1986.

[Leshchenko, Sotskov, 2005] N.M. Leshchenko, and Yu.N. Sotskov. Two-machine minimum-length shop-scheduling problems with uncertain processing times. In: Proceedings of XI International Conference Knowledge-DialogueSolution, June 20-24, Varna, Bulgaria, 375-381, 2005.

[Ng et al., 2006] C.T. Ng, N.M. Leshchenko, Yu.N. Sotskov and T.C.E. Cheng. Two-machine flow-shop minimum-length scheduling problem with interval processing times. Computers & Operations Research (submitted), 2006.

[Pinedo, 1995] M. Pinedo. Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, Englewood Cliffs. 1995.

[Slowinski, Hapke, 1999] R. Slowinski, and M. Hapke. Scheduling Under Fuzziness. Physica-Verlag, Heidelberg, New York. 1999.

[Shafransky, 2005] Ya.M. Shafransky. Scheduling problems with uncertain parameters: research directions and some results. Informatika. 3, 5-15, 2005 (in Russian).

Authors' Information Natalja M. Leshchenko United Institute of Informatics Problems of National Academy of Sciences of Belarus, Surganova str., 6, 220012, Minsk, Belarus; e-mail: leshchenko@newman.bas-net.by Yuri N. Sotskov Prof., DSc. United Institute of Informatics Problems of National Academy of Sciences of Belarus, Surganova str., 6, 220012, Minsk, Belarus; e-mail: sotskov@newman.bas-net.by 298 Intelligent Systems STABILITY ANALYSIS OF AN OPTIMAL ASSEMBLY LINE BALANCE WITH RESPECT TO UNCERTAIN OPERATION TIMES Yuri N. Sotskov Abstract: Two simple assembly line balancing problems are addressed. The first problem is to minimize number of linearly ordered stations for processing n partially ordered operations V = {1, 2,..., n} within the fixed cycle time c. This problem is denoted as SALBP-1. The second problem is to minimize cycle time for processing partially ordered operations V on the fixed set of m linearly ordered stations. The latter problem is denoted as SALBP-2.

The processing time t of operation i V are given before solving SALBP-1 and SALBP-2. However, during the i ~ life cycle of the assembly line the values t are definitely fixed only for the subset of automated operations V\V.

i ~ Another subset V V includes manual operations, for which it is impossible to fix exact processing times during ~ the whole life cycle of the assembly line. If j V, then operation times t can differ for different cycles of j production process. For the optimal line balance b of such an assembly line with vector t = (t, t, , t ) of the 1 2 n operation times, we investigate stability of its optimality with respect to possible variations of the processing times ~ t of the manual operations j V. In particular, we present necessary and sufficient conditions when optimality j of line balance b is stable for problem SALBP-1 (SALBP-2) with respect to variations of operation times t, j ~ j V. It is shown how to calculate the maximal value of independent variations of the processing times of all the manual operations, which definitely keep the feasibility and optimality of the line balance b.

Keywords: Scheduling, robustness and sensitivity analysis, assembly line.

ACM Classification Keywords: F.2.2 Nonnumerical algorithms and problems: sequencing and scheduling.

Introduction A single-model paced assembly line, which continuously manufactures homogeneous product in large quantities, is addressed. Terminology and main notations are given in survey [Baybars, 1986] and monograph [Scholl, 1999]. The assembly line is a sequence of m linearly ordered stations, which are linked by a conveyor belt or other material handling equipment. Each station of the assembly line has to perform the same set of operations repeatedly during the life cycle of the assembly line. Set of operations V, which have to be processed on the assembly line within one cycle time c, is fixed. Simple Assembly Line Balancing Problem (SALBP) is to find an optimal balance of the assembly line for cycle time c, i.e., to find a feasible assignment of all operations V into a minimal possible number m of stations. In [Scholl, 1999], abbreviation SALBP-1 is used for such a problem provided that cycle time c is fixed. Each operation i V is considered indivisible: an operation has to be completely processed on one station within one cycle time. All the m stations start simultaneously the sequences of their operations and buffers between stations are absent.

~ In this paper, it is assumed that set V includes operations of two main types. On the one hand, subset V V includes all the operations, for which it is impossible to fix exact processing times for the whole life cycle of the ~ assembly line (manual operations). On the other hand, operation i V \V is one with operation time t being i fixed during the life cycle of the assembly line (automated operations). The known technological factors define a partial order on the set of operations V. Digraph G = (V, A) with vertices V and arcs A defines partially ordered set of operations V = {1, 2,..., n}, which have to be processed on the assembly line within cycle time c. Without loss ~ ~ ~ ~ ~ ~ of generality, it is assumed that V = {1, 2,..., n} and V\V = {n + 1, n + 2,..., n}, where 0 n n.

~ = (t ~,t ~ ~+1 ~+The vectors of the operation times are denoted as t, t2,..., tn ), t = (tn, tn,..., tn ), t = ( t ) = ~ ~ (t, t,..., t ). Thus, the set of n operations may be presented as follows: V = {1, 2,..., n, n +1,..., n}. If 1 2 n ~ ~ ~ ~ n = 0, then V =. If n = n, then V = V. The assignment V = V V V of set of n operations V 1 2 m XII-th International Conference "Knowledge - Dialogue - Solution" to m linearly ordered stations S = (S, S,, S ) (i.e., partition of set V into m mutually disjoint non-empty subsets 1 2 m V, k {1, 2, , m}) is feasible operation assignment (called line balance) if the following two conditions hold.

k Condition 1: Feasible operation assignment does not violate the precedence constraints given by digraph G = (V, A), i.e., inclusion (i, j) A implies that operation i is assigned to station S : i Vk, and operation j is k assigned to station S: j Vl, such that 1 k l m.

Pages:     | 1 |   ...   | 67 | 68 || 70 | 71 |   ...   | 82 |



2011 www.dissers.ru -

, .
, , , , 1-2 .