Sequencing Problem with Maximum Lateness Criterion
This chapter is devoted to Minmax Regret 1|prec|L max . In this problem, for every job i ∈ J we are given an interval processing time \(\tilde{p}_i=[\underline{p}_i,\overline{p}_i]\) and an interval due date \(\tilde{d}_i=[\underline{d}_i,\overline{d}_i]
- PDF / 446,537 Bytes
- 7 Pages / 430 x 660 pts Page_size
- 7 Downloads / 195 Views
This chapter is devoted to Minmax Regret 1|prec|Lmax . In this problem, for every job i ∈ J we are given an interval processing time p˜i = [pi , pi ] and an interval due date d˜i = [di , di ]. A scenario S is a particular realization of the processing times and the due dates in the problem. The set of jobs is partially ordered by some arbitrary precedence constraints. A lateness of job i under scenario S is defined as follows: Li (π, S) = Ci (π, S) − dSi ,
(13.1)
where dSi is a due date of job i under scenario S. The cost of a given schedule under scenario S is as follows: n
F (π, S) = max Li (π, S), i=1
(13.2)
thus the cost is the maximal lateness in π under S. In the Minmax Regret 1| prec|Lmax problem we wish to find a feasible schedule π ∈ Π that minimizes the maximal regret. It turns out that this problem is polynomially solvable and we construct an algorithm whose running time is O(n4 ) in Section 13.2. This algorithm is a generalization of the well known algorithm designed by Lawler, which is used to solve the deterministic problem 1|prec|Lmax . We recall Lawler’s algorithm in Section 13.1.
13.1 Deterministic Problem and Lawler’s Algorithm If scenario S is fixed, then an optimal schedule under S can be obtained by solving the deterministic 1|prec|Lmax problem. This can be done in O(n2 ) time by means of the algorithm designed by Lawler [91]. In fact, Lawler’s algorithm can be applied to more general problem 1|prec|fmax , in which all functions fi (t) that measure the completion costs of jobs i ∈ J are nondecreasing and the objective can be expressed in the following way: F (π) = max fj (Cj (π)). i∈J
A. Kasperski: Discrete Optimization with Interval Data, STUDFUZZ 228, pp. 167–173, 2008. c Springer-Verlag Berlin Heidelberg 2008 springerlink.com
168
Sequencing Problem with Maximum Lateness Criterion
Lawler’s Algorithm n Require: n, (pi )n i=1 , (di )i=1 , prec. Ensure: The optimal schedule π. 1: D ← {1, . . . , n} 2: for r ← n downto 1 do 3: Find i ∈ D, which has no successor in D and has a maximal value of di 4: π(r) ← i 5: D ← D \ {i} 6: end for 7: return π Fig. 13.1. Lawler’s algorithm for solving problem 1|prec|Lmax
A version of Lawler’s algorithm for solving 1|prec|Lmax is shown in Figure 13.1. Lawler’s Algorithm is based on the following rule: if D is a subset of jobs, then we choose a job that has no successor in D and has a maximal value of a due date among all jobs in D. The selected job is processed as the last one among the jobs in D. At the beginning set D consists of all jobs. At each iteration the cardinality of D is decreased by one and the procedure is repeated until set D is empty. Finally, an optimal schedule is constructed. The time required for computing the optimal schedule is O(n2 ). If there are no precedence constraints between jobs, then the algorithm can be simplified. It is then enough to apply the following earliest due dates rule (EDD): order the jobs with respect to nondecreasing due dates. Obviously, this can be done in O(n log n) time. Observe that the processing times
Data Loading...
