Книги по разным темам Pages:     | 1 |   ...   | 66 | 67 | 68 | 69 | 70 |   ...   | 82 |

[Lbov, 2001] G.S. Lbov, V.M. NedelТko. A Maximum informativity criterion for the forecasting Several variables of different types. // Computer data analysis and modeling. Robustness and computer intensive methods. Minsk, 2001, vol 2, 43Ц48.

[NedelТko, 2004] S. V. NedelТko. A transitional matrix informativity criterion and forecasting heterogeneous time series. // Artificial Intelligence, №2, Ukraine, 2004, pp.145Ц149. (in Russian).

Authors' Information Victor Mikhailovich NedelТko - Institute of Mathematics SB RAS, Laboratory of Data Analysis, 660090, pr. Koptyuga, 4, Novosibirsk, Russia, e-mail: nedelko@math.nsc.ru Svetlana Valeryevna NedelТko - Institute of Mathematics SB RAS, Laboratory of Data Analysis, 630090, pr. Koptyuga, 4, Novosibirsk, Russia, e-mail: nedelko@math.nsc.ru A DOMINANT SCHEDULE FOR THE UNCERTAIN TWO-MACHINE SHOP-SCHEDULING PROBLEM Natalja Leshchenko, Yuri Sotskov Abstract: Non-preemptive shop-scheduling problem with random but bounded processing times is studied. In an uncertain version of a shop-scheduling problem there may not exist a unique schedule that remains optimal for all possible realizations of the job processing times t. We find necessary and sufficient conditions when there jm exists a dominant permutation that is an optimal JohnsonТs permutation for all possible realizations of the processing times t. Computational studies show the percentage of the problems solvable under these jm conditions for the cases of randomly generated instances with n 100 jobs.

Keywords: Scheduling, makespan, uncertainty.

ACM>

In spite of several developments, flow-shop scheduling problem remains largely unsolved (see [Gupta, Stafford, 2006]). In most of these developments, JohnsonТs rule and analysis methods play a significant role. In this paper we consider a shop-scheduling problem with interval processing times. A scheduling problem with interval processing times is rather general, since most events that are uncertain before scheduling may be considered as factors that vary the job processing times. The processing time may depend on the distance between machines, the type of transport used, traffic conditions, intervals of availability of machines, possible machine breakdowns, emergence of new unexpected jobs with high priority, early or late arrival of raw materials. In survey [Gupta, Stafford, 2006], there were presented 21 restrictions involved in the>

Problem Statement L First, we consider the non-preemptive flow-shop scheduling problem F 2 | t t tU | Cmax with random jm jm jm but bounded processing times. Two machines M = {M1, M } have to process n jobs J = {1, 2,..., n} with the same two-stage (machine) routes. All the n jobs are available to be processed from time = 0. In contrast to deterministic scheduling problem, it is assumed that processing time t of job j J by machine M M is jm m not fixed before scheduling. In a realization of the process, t may be equal to any real value between lower jm L bound t and upper bound tU being given before scheduling (the probability distribution of random jm jm processing time is unknown before scheduling). We address the stochastic flow-shop problem for the case when it is hard to obtain exact probability distributions for random but bounded processing times, and when assuming a specific probability distribution is not realistic before scheduling. (In such a case there may not exist a unique schedule that remains optimal for all possible realizations of the job processing times.) It has been observed that, although the exact probability distribution of the job processing times may be unknown in advance, upper and lower bounds on the job processing times are easy to obtain in many practical cases.

L If equality t = tU holds for each job j J and each machine M M, then problem jm jm m L F 2 | t t tU | Cmax turns into a deterministic flow-shop problem (denoted as F 2 || Cmax ) that is jm jm jm polynomially solvable due to [Johnson, 1954]. In contrast to deterministic problem F 2 || Cmax we call problem L F 2 | t t tU | Cmax an uncertain scheduling problem.

jm jm jm In paper [Johnson, 1954], it was proposed the O(nlog n) algorithm for constructing an optimal schedule for the deterministic flow-shop problem F 2 || Cmax. Permutation = (i1,i2,...,in12 ) that satisfies conditions min{til1,til+12} min{til+11,til 2}, l = 1,n12 -1, is called a Johnson's permutation. At least one optimal permutation for problem F 2 || Cmax is a JohnsonТs permutation. Note, that for the problem F 2 || Cmax optimal schedule may also be defined by permutation that does not satisfy the above JohnsonТs conditions.

Existence of a Dominant JohnsonТs Permutation for the Uncertain Flow-Shop Problem Let T denote a set of feasible vectors t = (t11, t12,..., tn1, tn2 ) of the job processing times:

L T ={ t | t t tU, j J, m M}.

jm jm jm XII-th International Conference "Knowledge - Dialogue - Solution" The set S of all feasible permutations (schedules) has the cardinality | S |= n!. Permutation i S dominates each other permutation S with k i if inequality Cmax (,t) Cmax (,t) hold for each S, k i k k where Cmax (,t) denotes objective value Cmax to the deterministic problem F 2 || Cmax with the vector t T i of the job processing times.

We call permutation i S a dominant JohnsonТs permutation to the uncertain problem L F 2 | t t tU | Cmax if for any feasible vector t T of the job processing times permutation i is a jm jm jm Johnson's permutation for the deterministic problem F 2 || Cmax with this vector t T of the job processing times.

L We consider the case when inequality t < tU holds for each job j J and each machine M M.

jm jm m For this case in [Leshchenko, Sotskov, 2005] the following theorem has been proven.

L Theorem 1 Let t < tU, j J, M M. Then there exists a dominant JohnsonТs permutation i S to jm jm m L the uncertain problem F 2 | t t tU | Cmax if and only if:

jm jm jm U L U L U L a) for any pair of jobs ji and j with tk1 tk 2, k = i, j (with tk 2 tk1, k = i, j, respectively) either ti1 t or j jU L tU tiL (either ti2 t or tU2 tiL ), j1 1 j2 j L L b) there exists at most one job j such that t < tU2,t < tU, and the following inequalities hold:

j1 j j2 jL U U L U U t max{ti1 | ti1 tiL }, t max{ti2 | ti2 tiL}.

2 j*1 j* Existence of a Dominant JacksonТs Pair of Permutations for the Uncertain Job-Shop Problem L We consider uncertain job-shop problem J 2 | t t tU | Cmax. Let J12 J be set of jobs with route jm jm jm (M1, M ) (first, job j J12 has to be processed by machine M, and then by machine M ), J21 J be set of 1 jobs with route (M, M1), and Jm J be set of jobs that are processed only by one machine M M.

2 m L If equality t = tU holds for each job j J and each machine m M, then problem jm jm L J 2 | t t tU | Cmax turns into a deterministic job-shop problem (denoted as J 2 || Cmax ). In paper jm jm jm [Jackson, 1956], it was proven that the optimal schedule for the problem J 2 || Cmax may be defined by the two permutations (, ), where is a permutation of jobs J1 J12 J21 on machine M, and is a permutation of jobs J2 J12 J21 on machine M. One can find an optimal schedule as a pair of permutations (, ) in the following form: ( = (12, 1, ), = (,, 12 ) ), where job j belongs to permutation 21 21 if and only if j Jl, l {1,2,12,21} and permutations 12 (permutation ) is the JohnsonТs permutation l of jobs of set J12 (of jobs of set J21 when machine M is the first machine in the route and machine M is the 2 second machine in the route). Since the order of the jobs in set J1 and in set J2 may be arbitrary, we can fix both permutations 1 and, e.g., we can order jobs in these permutations with respect to their job numbers.

We call pair of permutations (, ) a JacksonТs pair of permutations if it satisfies all the above conditions.

The jobs of set J12 (set J21 ) give uncertain flow-shop problem with machine route (M1, M ) (with opposite machine route (M, M1) for jobs of set J21 ). Therefore, for such a particular case of an uncertain flow-shop problem we can use Theorem 1, and so there exists a JohnsonТs permutation that is optimal for any vector t T of job processing times if and only if the corresponding conditions of Theorem 1 hold.

294 Intelligent Systems We call pair of permutations (, ) a dominant JacksonТs pair of permutations to the uncertain problem L J 2 | t t tU | Cmax if for any feasible vector t T of the job processing times pair of permutations jm jm jm (, ) is a Jackson's pair of permutations for the deterministic problem J 2 || Cmax with this vector t T of the job processing times.

L Again, we consider the case when inequality t < tU holds for each job j J and each machine M M.

jm jm m Theorem 7 in paper [Leshchenko, Sotskov, 2005] gives sufficient condition for existence of a solution to an uncertain job-shop problem. As a result, we can obtain the following condition for existence of a pair of permutations (, ) that is a dominant JacksonТs pair of permutations for the deterministic problem J 2 || Cmax with any feasible vector t T of the job processing times.

L Theorem 2 Let t < tU, j J, M M. Then there exists a dominant JacksonТs pair of permutations jm jm m L (, ) for the problem J 2 | t t tU | Cmax if for jobs from set J12 conditions a) and b) of Theorem jm jm jm hold, and for jobs from set J21 the corresponding conditions a) and b) of Theorem 1 hold.

Computational Results L In this section, we consider randomly generated uncertain flow-shop problems F 2 | t t tU | Cmax and jm jm jm answer experimentally the question of how many uncertain instances have a JohnsonТs permutation that is optimal for all corresponding deterministic problems F 2 || Cmax with any feasible vector t T of the job L processing times. For each randomly generated instance F 2 | t t tU | Cmax we tested whether jm jm jm condition of Theorem 1 held.

The computational algorithm was coded in MATLAB. For the computational experiments, we used an AMD MHz processor with 1024 MB main memory. For all instances we made 1000 tests in each series (for each combination of n and L). Of course, the running time increases with increasing the product nL. Fortunately, the running time for our analysis remains rather small (less than 4 seconds) for all series under consideration.

Random instances were generated as follows. First, we tested problems with УshortФ intervals of the job processing times:

n { 5, 10, 15, Е, 100} jobs, with integer processing times uniformly distributed in the range [1,1000], and L {1, 2, 3, Е, 10}.

For each operation, the lower bound was randomly generated and the upper bound was computed as follows:

L tU = t + L.

jm jm We tested also problems with УlongФ intervals of the job processing times:

n {5, 10, 15, Е, 100} jobs, with integer processing times uniformly distributed in the range [1,1000], and L {1, 2, 3, Е, 10}.

For each operation, the lower bound was randomly generated and the upper bound was computed as follows:

L tU = t (1 + L% /100%).

jm jm Tables 1 - 4 present the percentage of instances in the series for which conditions of Theorem 1 hold.

Along with the processing times uniformly distributed in the range [1,1000], we tested the cases when the processing times are uniformly distributed in the range [1,10000]. The computational results for the latter problems are given in Tables 2 and 4, which are analogous to Tables 1 and 3.

XII-th International Conference "Knowledge - Dialogue - Solution" L L Theoretically, the case with tU = t (1 + L% /100%) seems to be harder than that with tU = t + L since jm jm jm jm lengths of the intervals of the job processing times increase when value of lower bound increases. From our experiment, it follows that increasing simultaneously both numbers n and L decreases the number of solvable instances. Comparing Tables 3 and 4 show that there are no computational differences between cases with УlongФ intervals and the processing times uniformly distributed in the range [1,1000] and in the range [1,10000].

These problems are the hardest ones for our analysis based on Theorem 1.

L The easiest> Pages:     | 1 |   ...   | 66 | 67 | 68 | 69 | 70 |   ...   | 82 |    Книги по разным темам