Sequencing Problem with Weighted Number of Late Jobs
In this chapter we discuss Minmax Regret 1|p i = 1| ∑ w i U i . In this problem all jobs have unit processing times, that is p i = 1 for all i ∈ J, and all jobs have precise due dates d i , i ∈ J. We also assume that there are no precedence constraints
- PDF / 438,920 Bytes
- 8 Pages / 430 x 660 pts Page_size
- 64 Downloads / 169 Views
In this chapter we discuss Minmax Regret 1|pi = 1| wi Ui . In this problem all jobs have unit processing times, that is pi = 1 for all i ∈ J, and all jobs have precise due dates di , i ∈ J. We also assume that there are no precedence constraints between jobs. For every job i ∈ J there is given an interval weight w ˜i = [wi , w i ]. Thus a scenario is a particular realization of the uncertain weights. A job i ∈ J is said to be late in schedule π if Ci (π) = |P (π, i)| > di ; otherwise job i is said to be on-time in π. Notice that the fact of being late or not does not depend on a particular scenario, since all processing times and all due dates in the problem are precise. Let us define ⎧ ⎨ 1 if C (π) > d i i Ui (π) = ⎩ 0 if C (π) ≤ d i
i
Hence Ui (π) = 1 if and only if job i is late in π. The cost of a given schedule π under scenario S is expressed as follows: F (π, S) =
n
wiS Ui (π).
i=1
So, the cost is the weighted number of late jobs in π under S. In the Minmax Regret 1|pi = 1| wi Ui problem we seek a schedule which minimizes the maximal regret. If scenario S is fixed, then the optimal schedule under this scenario can be constructed in O(n2 ) time by a version of the greedy algorithm. It follows from the matroidal structure of the problem, which is discussed in Section 14.1. It turns out that both the deterministic problem and its minmax regret version can be reduced to a certain matroidal combinatorial optimization problem. This matroidal problem is a generalization of the polynomially solvable Minmax Regret Minimum Selecting Items, which was discussed in Chapter 5. However, the complexity status of Minmax Regret 1|pi = 1| wi Ui is unknown. In Section 14.2 we show an efficient method of preprocessing the problem. Finally, in A. Kasperski: Discrete Optimization with Interval Data, STUDFUZZ 228, pp. 175–182, 2008. c Springer-Verlag Berlin Heidelberg 2008 springerlink.com
176
Sequencing Problem with Weighted Number of Late Jobs
Section 14.3 we construct a MIP model for solving the problem and we present the results of some computational tests.
14.1 Matroidal Structure of the Problem It turns out that in order to solve the problem it is enough to consider only some particular schedules, namely the canonical ones. A schedule π is said to be in a canonical form if all on-time jobs are processed before all late jobs in π and all on-time jobs are ordered with respect to nondecreasing due dates. In other words, in a canonical schedule we first process all on-time jobs in order of nondecreasing due dates, and we process then all the remaining (late) jobs in any order. The following proposition characterizes the canonical schedules: Proposition 14.1. For every schedule π there exists a canonical schedule π1 such that F (π1 , S) ≤ F (π, S) for all scenarios S ∈ Γ . Proof. If π is a canonical schedule, then we are done. If not, denote by O the set of on-time jobs in π and transform π into π1 in the following way: move all late jobs in π after the last on-time job in π and order the on-time jobs with respect t
Data Loading...
