| 学籍番号 | 90129028 | 所属研究室 | 藤重研 |
| 氏名 | 江 口 明 伸 | ||
| タイトル | Parametric Generalized Maximum Flows and Applications | ||
|
1. Introduction We consider the problem of preemptive scheduling k jobs with l uniform machines, where each job j has a processing requirement p(j) and a due date d(j). Denoting by C(j) the completion time for a job j, we allow the case C(j) is greater than d(j). Each job j also has a positive weight w(j). Here, we define the weighted tardiness for each job j as w(j)tau(j) where tau(j)=max{0,C(j)-d(j)}, and the problem is to find a feasible schedule that minimizes the maximum weighted tardiness, i.e., min max_j w(j)tau(j). This problem was formulated by Serafini (1996) and was reduced to a maximum flow problem in a parametric network. We extend this problem to the case when machines are non-uniform, which can be reduced to a generalized maximum flow problem in a network with gains whose underlying graph is same as that in Serafini's model. 2. Algorithms In the parametric network where only the arcs incident to the source or the sink have parametric capacities, we can solve a maximum flow for each given parameter by GGT's algorithm (1989). This algorithm was extended by McCormick (1999) to the case where some arcs not incident to the source or the sink have parametric capacities, and was applied to the scheduling problem formulated by Serafini (1996). Denoting the number of vertices and arcs by n and m, respectively, these two algorithms with the dynamic tree data structure by Sleator and Tarjan (1983) run in O(n m log(n^2/m)) time, which is the same time bound as that for a single maximum flow problem. A generalized flow network has a gain factor gamma(a) for each arc a. If varphi(a) units of flow enter an arc a, then gamma(a)varphi(a) units arrive at the end of a. The fat path algorithm by Goldberg, Plotkin and Tardos (1991) can solve a generalized maximum flow problem in O(m^2 n^2 log n log^2 B) time, where B denotes the largest integer among the numerators and the denominators representing the capacities, the gain factors and the initial excesses. 3. Applications We guess the minimum of the maximum weighted tardiness tau^*, which induces a derived due date bar{d}(j)=d(j)+tau^*/w(j), so that the maximum weighted tardiness is at most tau^* if and only if there is a feasible schedule for bar{d}. Hence it is enough to find a feasible schedule for bar{d} that minimizes tau^*. We denote by J_i a nonempty set of jobs to be processed with a machine i, by M_j a nonempty set of machines to process a job j and by t(i,j) the amount of the total processing time for a job j performed on a machine i, so that p(j)=sum_{i in M_j}t(i,j)sigma(i,j) (j in J). It is well known that putting the jobs in order of earliest due date (EDD) first minimizes tardiness on a single machine. Let pi^i(l) denote EDD order of the jobs in J_i, so that sum_{k=1}^l t(i,pi^i(k)) <= bar{d}(pi^i(l)) (i in M,l=1,2,..,pi^i(|J_i|)). Now we can define a flow network N^* to solve our problem. There is a path of |J_i| arcs for each machine i, whose lth last arc (v_{pi^i(l+1)}^i,v_{pi^i(l)}^i) is associated with a job pi^i(l) and is of capacity bar{d}(pi^i(l)) and of gain 1. The paths have a single common vertex s^+=v_{pi^i(|J_i|+1)}^i for all i, which is the source. We have a vertex s_j for each job j and an arc (v_j^i,s_j) with infinite capacity and gain sigma(i,j) for each i in M_i. There is also the sink s^- and arcs (s_j,s^-) for j in J with capacity p(j) and gain 1. This model is verified by identifying each t(i,j) with the flow value on an arc (v_j^i,s^-). Theorem : There is a flow saturating (s_j,s^+) (j in J) in N^* if and only if there is a feasible schedule for tau^*. 4. Conclusion We have reduced a preemptive scheduling problem with k jobs and l non-uniform machines to a generalized maximum flow problem. It takes O(k^4 l^4 log k log^2B) time to compute a maximum flow in N^* with capacities for each guess at tau^*. To minimize tau^*, we find the optimal parametric value by the binary search and by iterating the fat path algorithm for each value. This gives a polynomial-time algorithm. |
|||