- 上一篇：残余应力状态的影响刀具寿命英文文献和中文翻译
- 下一篇：噪音工程齿轮模型英文文献和中文翻译
4. If x > 1 and y > 1, Px,y:= max{Px,y-1,P x-1,y’ ,P x-1,y-1 +Wx,y}
(1) is the basic case: If we only consider the first crane and the first job, we will assign this job to the crane if the job can be done by the crane. (2) and (3) are both special cases, i.e., when there is only one node in each part of the bipartite graph. As these are symmetrical, we need consider only (2). For crane c1and job jy, we have two choices: either, assign jyto c1, or, assign a job from {j1, . . . , jy−1}to c1. This is because at most one job can be assigned to this first crane. The throughput for the first choice is W1,y while the throughput for the second choice is P1,y−1 , which represents the maximum throughput if we assign a job among j1, j2, . . . , jy-1 to crane c1. To achieve the cumulative optimal, we choose the larger of these. (4) is the general case in the DP algorithm. For cxand job jy(x > 1, y > 1), we have three choices:
• Leave job jy unassigned . We are reduced to assigning cranes c1, c2, . . . , cx to jobs j1, j2, . . . , jy-1. By induction, the optimal value is then Px,y-1;
• Leave crane cx unassigned . We are reduced to assigning cranes c1, c2, . . . , cx-1 to jobs j1, j2, . . . , jy. By induction, the optimal value is then Px-1,y;
• Assign crane cxto job jy(or, leave both unassigned if they are not assignable to each other). In this case, the total throughput is the throughput from this assignment plus the throughput from assigning cranes c1, c2, . . . , cx-1 to jobs j1, j2, . . . , jy-1. Hence, the value is Px-1,y-1+Wx,y.
Taking the maximum of these throughput values, the optimal solution is then the final partial optimal solution Pm,n obtained.
3.2.2 A Proof of Optimal Substructure
We provide an outline a proof that the problem defined in this section possesses optimal substructures necessary in using DP. An important property for Px,yis: Px,y≥Px’,y’,if x ≥ x’and y ≥ y’(*), which is easily verified since Px,y≥ Px,y-1 and Px,y≥ Px-1,y. We can now verify the four cases given above by induction:
1. If x = 1 and y = 1, clearly P1,y = Wx,1 is the only solution and must be optimal
2. If (x, y)∈R’x,y, then Px,y’≤Pak-1,bk-1+Wx,y. By (*), we know Px-1,y−1 ≥Pak-1,b-1 since x − 1 ≥ ak-1, y-1 ≥ bk-1. So Px,y’≤ Px-1,y-1+Wx,y. Because Px,y≥Px-1,y-1+ Wx,y, we get Px,y≥ Px,y’ , which contradicts our assumption Px,y’> Px,y. Hence, Px,y is the optimal solution.
We can conclude that Px,y is the optimal solution for all (x, y), 1 ≤ x ≤ m, 1 ≤ y ≤ n,
3.3 The Time Complexity of the Algorithm
The computation for every partial solution Px,y is in constant time, so the time complexity for this algorithm is O(mn).
4 Scheduling with the Neighborhood Constraint
4.1 The Problem
In this problem, both the Non-crossing constraint and the Neighborhood constraint are considered. In addition to the Non-crossing constraint, we use the set S= {s1, s2, . . . , sm} to represent the Neighborhood constraint associated with the cranes. Here sx= k if crane cxperforms job jyand job jz(a ≤ z ≤ b, z= y) cannot be worked on by any other crane, where a = max{1, y − k}and b = min{y + k, m}. In other words, if crane cxperforms job jy, the job “interval” centered at y with length 2k + 1 is affected by crane cxwhen sx= k.
We seek a solution set R = {(p, q)|1 ≤ p ≤ m, 1 ≤ q ≤ n, Wp,q> 0} satisfying:
1. For all (p1, q1), (p2, q2) ∈ R, p1< p2if and only if q1< q2(Non-crossing constraint)
-
会计师事务所任期与审计...
-
ADO.NET结构与概述英文文献和中文翻译
-
信息系统开发与数据库开...
-
机器人学入门力学与控制英文文献和中文翻译
-
园林植物景观的园林绿化...
-
桥式起重机智能防摆控制英文文献和中文翻译
-
起重机升降传感器系统英文文献和中文翻译
NFC协议物理层的软件实现+文献综述
江苏省某高中学生体质现状的调查研究
现代简约美式风格在室内家装中的运用
g-C3N4光催化剂的制备和光催化性能研究
高警觉工作人群的元情绪...
浅析中国古代宗法制度
巴金《激流三部曲》高觉新的悲剧命运
上市公司股权结构对经营绩效的影响研究
中国传统元素在游戏角色...
C++最短路径算法研究和程序设计