Measures of problem uncertainty for scheduling with interval processing times

The paper deals with scheduling under uncertainty of the job processing times. The actual value of the processing time of a job becomes known only when the schedule is executed and may be equal to any value from the given interval. We propose an approach which consists of calculating measures of problem uncertainty to choose an appropriate method for solving an uncertain scheduling problem. These measures are based on the concept of a minimal dominant set containing at least one optimal schedule for each realization of the job processing times. For minimizing the sum of weighted completion times of the \(n\) jobs to be processed on a single machine, it is shown that a minimal dominant set may be uniquely determined. We demonstrate how to use an uncertainty measure for selecting a method for finding an effective heuristic solution of the uncertain scheduling problem. The efficiency of the heuristic \(O(n\log n)\)-algorithms is demonstrated on a set of randomly generated instances with \(100 \le n \le 5{,}000.\) A similar uncertainty measure may be applied to many other scheduling problems with interval processing times.

This research was supported by the National Science Council of Taiwan (Yu.N. Sotskov and T.-C. Lai) and by DAAD (Y.N. Sotskov and F. Werner). The authors are grateful to N.G. Egorova for coding the algorithms developed and to anonymous referees for very helpful remarks and suggestions on an earlier draft of the paper.

Authors and Affiliations

1. United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street, 6, 220012 , Minsk, Belarus

   Yuri N. Sotskov

2. Department of Business Administration, National Taiwan University, 2nd Management Building, 85, Sector 4, Roosevelt Road, 10672 , Taipei, Taiwan

   Tsung-Chyan Lai

3. Faculty of Mathematics, Otto-von-Guericke-University, Universitätsplatz 2, 39106 , Magdeburg, Germany

   Frank Werner

Corresponding author

Correspondence to Frank Werner.

Appendix

In the proof of Theorem 5, Lemmas 1–3 from Sotskov and Lai (2012) are used.

Lemma 1

Sotskov and Lai (2012) In any optimal permutation for the instance \(1 |p | \sum w_iC_i,\) job \(J_u\in \mathcal{J }\) precedes job \(J_v\in \mathcal{J }\) if and only if \(\frac{w_{u}}{p_{u}} > \frac{w_{v}}{p_{v}}.\)

Lemma 2

Sotskov and Lai (2012) For the instance \(1 |p | \sum w_iC_i,\) an optimal permutation is unique if and only if \(\frac{w_{u}}{p_{u}} \ne \frac{w_{v}}{p_{v}}\) for any jobs \(J_u \in \mathcal{J }\) and \(J_v \in \mathcal{J }.\)

Lemma 3

Sotskov and Lai (2012) For the instance \(1 |p | \sum w_iC_i,\) there exist both an optimal permutation with job \(J_u\in \mathcal{J }\) preceding job \(J_v\in \mathcal{J }\) and one with job \(J_v\) preceding job \(J_u\) if and only if \(\frac{w_{u}}{p_{u}} = \frac{w_{v}}{p_{v}}.\)

Proof of Theorem 5

For any pair of jobs \(J_t \in \mathcal{J }\) and \(J_v \in \mathcal{J },\) we examine all arrangements of the segments \([\frac{w_{t}}{p_{t}^\mathrm{U}}, \frac{w_{t}}{p_{t}^\mathrm{L}}]\) and \([\frac{w_{v}}{p_{v}^\mathrm{U}}, \frac{w_{v}}{p_{v}^\mathrm{L}}].\) W.l.o.g. we assume \(\frac{w_{v}}{p_{v}^\mathrm{U}} \le \frac{w_{t}}{p_{t}^\mathrm{U}}.\) Due to the job symmetry, it is sufficient to examine the following cases (a)–(i).

Case (a): \(\frac{w_{t}}{p_{t}^\mathrm{U}} < \frac{w_{t}}{p_{t}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}} < \frac{w_{v}}{p_{v}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{L}} < \frac{w_{t}}{p_{t}^\mathrm{U}}.\) Thus, inequality \(\frac{w_{v}}{p_{v}} < \frac{w_{t}}{p_{t}} \) holds for each scenario \(p \in T.\) Due to Lemma 1, in all optimal permutations for the instance \(1 |p | \sum w_iC_i\) with a scenario \(p \in T,\) job \(J_t\) precedes job \(J_v.\) Thus, in each permutation of a minimal dominant set \(S(T)\) job \(J_t\) precedes job \(J_v.\)

Case (b): \(\frac{w_{t}}{p_{t}^\mathrm{U}}<\frac{w_{t}}{p_{t}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}}<\frac{w_{v}}{p_{v}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{L}} \le \frac{w_{t}}{p_{t}^\mathrm{U}}.\) If for the scenario \(p \in T\) at least one of the conditions \(\frac{w_{v}}{p_{v}} \ne \frac{w_{v}}{p_{v}^\mathrm{L}}\) or \(\frac{w_{t}}{p_{t}} \ne \frac{w_{t}}{p_{t}^\mathrm{U}}\) holds, then arguing as in case (a), we obtain that in each permutation of any set \(S(T),\) job \(J_t\) precedes job \(J_v.\) For the remaining scenario \(p^{\prime } = (p^{\prime }_1,p^{\prime }_2, \ldots , p^{\prime }_n) \in T\) with \(\frac{w_{v}}{p^{\prime }_{v}} = \frac{w_{v}}{p_{v}^\mathrm{L}}\) and \(\frac{w_{t}}{p^{\prime }_{t}} = \frac{w_{t}}{p_{t}^\mathrm{U}},\) we obtain \(\frac{w_{v}}{p^{\prime }_{v}} = \frac{w_{t}}{p^{\prime }_{t}}.\) Due to Lemma 3, for the instance \(1 |p^{\prime }|\sum w_iC_i,\) there exist both an optimal permutation of the form \(\pi _l = (\ldots , J_{t}, \ldots , J_{v}, \ldots ) \in S\) and one of the form \(\pi _m = (\ldots , J_{v}, \ldots , J_{t}, \ldots ) \in S.\) However, no permutation of the form \(\pi _m\) may be contained in a minimal dominant set, since such a permutation will be redundant.

Indeed, a permutation of the form \(\pi _l\) will be definitely contained in any set \(S(T)\) because of the scenario \(p \in T\) with \(p \ne p^{\prime }.\) The permutation \(\pi _l\) provides an optimal solution for the instance \(1 |p^{\prime }|\sum w_iC_i.\) If the set \(S(T)\) contains a permutation of the form \(\pi _m,\) then the dominant set \(S(T)\) is not minimal. Thus, in each permutation of any set \(S(T),\) job \(J_t\) has to precede job \(J_v.\)

Case (c): \(\frac{w_{t}}{p_{t}^\mathrm{U}} < \frac{w_{t}}{p_{t}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}} < \frac{w_{v}}{p_{v}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{L}} > \frac{w_{t}}{p_{t}^\mathrm{U}}.\) The length of the intersection of the segments \([\frac{w_{t}}{p_{t}^\mathrm{U}}, \frac{w_{t}}{p_{t}^\mathrm{L}}]\) and \([\frac{w_{v}}{p_{v}^\mathrm{U}}, \frac{w_{v}}{p_{v}^\mathrm{L}}]\) must be strictly positive. There exist a scenario \(p \in T\) with \(\frac{w_{t}}{p_{t}} > \frac{w_{v}}{p_{v}}\) and a scenario \(p^{\prime }\in T\) with \(\frac{w_{t}}{p^{\prime }_{t}} < \frac{w_{v}}{p^{\prime }_{v}}.\) Due to Lemma 1, in all optimal permutations for the instance \(1 |p | \sum w_iC_i,\) job \(J_t\) precedes job \(J_v,\) and in all optimal permutations for the instance \(1 |p^{\prime }| \sum w_iC_i,\) job \(J_v\) precedes job \(J_t.\) Thus, any minimal dominant set for the instance \(1 |p_{i}^\mathrm{L} \le p_{i} \le p_{i}^\mathrm{U} | \sum w_iC_i\) contains both a permutation of the form \(\pi _l = (\ldots , J_{t}, \ldots ,J_{v}, \ldots ) \in S\) and one of the form \(\pi _m = (\ldots , J_{v},\ldots , J_{t}, \ldots ) \in S.\)

Case (d) with \(\frac{w_{t}}{p_{t}^\mathrm{U}} = \frac{w_{t}}{p_{t}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}} < \frac{w_{v}}{p_{v}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{L}} < \frac{w_{t}}{p_{t}^\mathrm{U}}\) is examined as case (a).

Case (e) with \(\frac{w_{t}}{p_{t}^\mathrm{U}} = \frac{w_{t}}{p_{t}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}} < \frac{w_{v}}{p_{v}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{L}} = \frac{w_{t}}{p_{t}^\mathrm{U}}\) is examined as case (b).

Case (f) with \(\frac{w_{t}}{p_{t}^\mathrm{U}} = \frac{w_{t}}{p_{t}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}} < \frac{w_{v}}{p_{v}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{L}} < \frac{w_{t}}{p_{t}^\mathrm{U}} < \frac{w_{v}}{p_{v}^\mathrm{U}}\) is examined as case (c).

Case (g) with \(\frac{w_{t}}{p_{t}^\mathrm{U}} = \frac{w_{t}}{p_{t}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}} < \frac{w_{v}}{p_{v}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}} = \frac{w_{t}}{p_{t}^\mathrm{U}}\) is examined as case (b).

Case (h): \(\frac{w_{t}}{p_{t}^\mathrm{U}} = \frac{w_{t}}{p_{t}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}} = \frac{w_{v}}{p_{v}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{L}} < \frac{w_{t}}{p_{t}^\mathrm{U}}.\) The processing times of the jobs \(J_t\) and \(J_v\) are fixed and \(\frac{w_{v}}{p_{v}} < \frac{w_{t}}{p_{t}}.\) Due to Lemma 1, in all optimal permutations for the instance \(1 |p | \sum w_iC_i,\) job \(J_v\) precedes job \(J_t.\) Hence, in each permutation of any minimal dominant set, job \(J_t\) has to precede job \(J_v.\)

Case (i): \(\frac{w_{t}}{p_{t}^\mathrm{U}} = \frac{w_{t}}{p_{t}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{U}} = \frac{w_{v}}{p_{v}^\mathrm{L}}, \frac{w_{v}}{p_{v}^\mathrm{L}} = \frac{w_{t}}{p_{t}^\mathrm{U}}.\) The processing times of the jobs \(J_t\) and \(J_v\) are fixed: \(p_{t}^\mathrm{L} = p_{t}^\mathrm{U}=p_t, p_{v}^\mathrm{L} = p_{v}^\mathrm{U}=p_t,\) and \(\frac{w_{v}}{p_{v}} = \frac{w_{t}}{p_{t}}.\) Due to Lemma 2 (Lemma 3, respectively) for each instance \(1 |p | \sum w_iC_i,p \in T,\) an optimal permutation is not unique (there exist both an optimal permutation \(\pi _l \in S\) with job \(J_t\) preceding job \(J_v\) and an optimal permutation \(\pi _m \in S\) with job \(J_v\) preceding job \(J_t\)). The jobs \(J_t\) and \(J_v\) generate two different minimal dominant sets \(S(T)\) and \(S^{\prime }(T).\) If case (i) occurs, then \(|\mathcal{J }_r| \ge 2,r =\frac{w_{t}}{p_{t}^\mathrm{U}} = \frac{w_{t}}{p_{t}^\mathrm{L}} = \frac{w_{v}}{p_{v}^\mathrm{U}} = \frac{w_{v}}{p_{v}^\mathrm{L}},\) and vice versa. Since the above treatment in cases (a)–(i) is applicable to any pair of jobs of the set \(\mathcal{J },\) we complete the proof as follows.

Sufficiency Assume that there does not exist an \(r \in [a, b]\) with \(|\mathcal{J }_r| \ge 2.\)

This means that there is no pair of jobs \(J_t \) and \(J_v \) in the set \(\mathcal{J }\) with their weight-to-process ratios satisfying case (i). In each of the remaining cases (a)–(h), the order of the jobs \(J_t \in \mathcal{J }\) and \(J_v \in \mathcal{J }\) is defined in any permutation from a set \(S(T)\) as follows. Job \(J_t\) precedes job \(J_v\) in the permutation \(\pi _l \in S(T)\) in the cases (a), (b), (d), (e) and (h). Job \(J_v\) precedes job \(J_t\) in the permutation \(\pi _m \in S(T)\) in case (g). Both orders of these two jobs are realized in the permutations \(\pi _l \in S(T)\) and \(\pi _m \in S(T)\) which have to be contained in any minimal dominant set in each of the cases (c) and (f). Thus, a minimal dominant set \(S(T)\) is unique for an instance \(1 |p_{i}^\mathrm{L} \le p_{i} \le p_{i}^\mathrm{U} | \sum w_iC_i\) if there is no \(r \in [a, b]\) with \(|\mathcal{J }_r| \ge 2.\)

Necessity Let the minimal dominant set \(S(T)\) be uniquely determined for the instance \(1 |p_{i}^\mathrm{L} \le p_{i} \le p_{i}^\mathrm{U} | \sum w_iC_i.\) By contradiction, we assume that there exists an \(r \in [a, b]\) with \(|\mathcal{J }_r| \ge 2.\) The inequality \(|\mathcal{J }_r| \ge 2\) holds only if case (i) occurs for the jobs from \(\mathcal{J }_r.\) There exist at least two minimal dominant sets \(S(T)\) and \(S^{\prime }(T).\) This contradiction completes the proof.

Reprints and permissions