Information Technology Reference
In-Depth Information
5
Conclusions
In [12], an
O
(
n
2
)
algorithm has been developed for calculating a permutation
π
t
∈ S
with the largest dimension and volume of a stability box
SB
(
π
t
,T
)
. In Section 3, we
proved Properties 1 - 6 of a stability box allowing us to derive an
O
(
n
log
n
)
algorithm
for calculating such a permutation
π
t
∈ S
max
. The dimension and volume of a stabil-
ity box are efficient invariants of the uncertain data
T
, as it was shown in simulation
experiments on a PC reported in Section 4.
The results that we presented may be generalized to the problem
1
|prec,p
i
≤ p
i
≤
p
i
|
w
i
C
i
, where the precedence constraints are given a priori on the set of jobs. If the
deterministic problem
1
|prec|
w
i
C
i
for a particular type of precedence constraints is
polynomially solvable, then the above results may be used for the uncertain counterpart
1
|prec,p
i
≤ p
i
≤ p
i
|
w
i
C
i
. In the latter problem, the dominance digraph
(
J , A
)
contains the arc
(
J
u
,J
v
)
only if this arc does not violate the precedence constraint given
between the jobs
J
u
and
J
v
apriori.
Acknowledgements.
The first and second authors were supported in this research by
National Science Council of Taiwan. The authors are grateful to Natalja G. Egorova for
coding algorithm MAX-STABOX and other contributions.
References
1. Daniels, R., Kouvelis, P.: Robust scheduling to hedge against processing time uncertainty in
single stage production. Management Science 41(2), 363-376 (1995)
2. Kasperski, A.: Minimizing maximal regret in the single machine sequencing problem with
maximum lateness criterion. Operations Research Letters 33, 431-436 (2005)
3. Kasperski, A., Zelinski, P.: A 2-approximation algorithm for interval data minmax regret
sequencing problem with total flow time criterion. Operations Research Letters 36, 343-344
(2008)
4. Lai, T.-C., Sotskov, Y.: Sequencing with uncertain numerical data for makespan minimiza-
tion. Journal of the Operations Research Society 50, 230-243 (1999)
5. Lai, T.-C., Sotskov, Y., Sotskova, N., Werner, F.: Optimal makespan scheduling with given
bounds of processing times. Mathematical and Computer Modelling 26(3), 67-86 (1997)
6. Pinedo, M.: Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, Englewood Cliffs
(2002)
7. Sabuncuoglu, I., Goren, S.: Hedging production schedules against uncertainty in manufac-
turing environment with a review of robustness and stability research. International Journal
of Computer Integrated Manufacturing 22(2), 138-157 (2009)
8. Slowinski, R., Hapke, M.: Scheduling under Fuzziness. Physica-Verlag, Heidelberg (1999)
9. Smith, W.: Various optimizers for single-stage production. Naval Research Logistics Quar-
terly 3(1), 59-66 (1956)
10. Sotskov, Y., Egorova, N., Lai, T.-C.: Minimizing total weighted flow time of a set of jobs
with interval processing times. Mathematical and Computer Modelling 50, 556-573 (2009)
11. Sotskov, Y., Egorova, N., Werner, F.: Minimizing total weighted completion time with uncer-
tain data: A stability approach. Automation and Remote Control 71(10), 2038-2057 (2010)
Search WWH ::
Custom Search