The Stability Box for Minimizing TotalWeighted Flow Time under Uncertain Data - Simulation and Modeling Methodologies, Technologies and Application - page 35

The Stability Box for Minimizing Total Weighted Flow
Time under Uncertain Data

Yuri N. Sotskov 1 , Tsung-Chyan Lai 2 , and Frank Werner 3

1 United Institute of Informatics Problems, National Academy of Sciences of Belarus,
Surganova Str 6, Minsk, Belarus
2 Department of Business Administration, National Taiwan University,
Roosevelt Rd 85, Taipei, Taiwan
3 Faculty of Mathematics, Otto-von-Guericke-University, Magdeburg, Germany
[e-mail], [e-mail],
[e-mail]

Abstract. We consider an uncertain single-machine scheduling problem, in which
the processing time of a job can take any real value from a given closed interval.
The criterion is to minimize the sum of weighted completion times of the n jobs, a
weight being associated with each job. For a job permutation, we study the stability
box, which is a subset of the stability region. We derive an O ( n log n ) algorithm
for constructing a job permutation with the largest dimension and volume of a sta-
bility box. The efficiency of such a permutation is demonstrated via a simulation
on a set of randomly generated instances with 1000 ≤ n ≤ 2000 . If several per-
mutations have the largest dimension and volume of a stability box, the developed
algorithm selects one of them due to a mid-point heuristic.

Keywords: Single-machine scheduling, Uncertain data, Total weighted flow
time, Stability analysis.

1 Introduction

In real-life scheduling, the numerical data are usually uncertain. A stochastic [6] or a
fuzzy method [8] are used when the job processing times may be defined as random
variables or as fuzzy numbers. If these times may be defined neither as random vari-
ables with known probability distributions nor as fuzzy numbers, other methods are
needed to solve a scheduling problem under uncertainty [1,7,13]. The robust method
[1,2,3] assumes that the decision-maker prefers a schedule hedging against the worst-
case scenario. The stability method [4,5,10,11,12,13] combines a stability analysis, a
multi-stage decision framework and the solution concept of a minimal dominant set of
semi-active schedules.
In this paper, we implement the stability method for a single-machine problem with
interval processing times of the n jobs (Section 2). In Section 3, we derive an O ( n log n )
algorithm for constructing a job permutation with the largest dimension and volume of
a stability box. Computational results are presented in Section 4. We conclude with
Section 5.