[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 Classification Keywords: F.2.2 Non-numerical algorithms and problems: sequencing and scheduling Introduction In scheduling theory, many systems under consideration assume complete information about the scheduling problems to be solved and a static environment within the schedule to be executed. However, the real world is not static: machines break down, activities take longer to execute than expected, and jobs may be added or canceled. There exist a lot of approaches concerning management of uncertainty in scheduling (see surveys [Aytug et al., 2005; Davenport, Beck, 2000; Gupta, Stafford, 2006]). The stochastic method [Elmaghraby, Thoney, 2000; Pinedo, 1995] for dealing with uncertainty is useful when the schedule has enough prior information to characterize the probability distributions of the random processing times and there are a large number of realizations of the similar processes. In the particular case of the stochastic scheduling problem, random processing times may be controllable, and the objective is to choose the optimal processing times (which are under the control of the decision-maker) and the optimal schedule with the chosen processing times. For such a problem, the objective function depends on both the job processing times and the job completion times (see [Jansen, Mastrolilli, Solis-Oba, 2005]). The current trends in the field of scheduling under the fuzziness notion 292 Intelligent Systems have been presented in [Slowinski, Hapke, 1999]. In the field of operations research for the problems under uncertainty auxiliary criteria are often used. The most popular auxiliary criteria are criteria by Wald, Hurwicz and Savage (see [Shafransky, 2005] for survey).

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 classical flow-shop problem F || Cmax with fixed job processing times, where criterion Cmax denotes minimization of schedule length. Nine of these 21restrictions addressed the criterion and type of the processing system. All the remaining restrictions may be overcome by using the suitable intervals for possible variations of the job processing times.

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 class of problems in our experiments was that with condition tU = t + L and processing times jm jm uniformly distributed in the range [1,10000]. Obviously, in this case uncertain problem L F 2 | t t tU | Cmax is closed to the deterministic problem F 2 || Cmax.

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.