- 上一篇：残余应力状态的影响刀具寿命英文文献和中文翻译
- 下一篇：噪音工程齿轮模型英文文献和中文翻译
2. For all (p, q) ∈ R, if 1 ≤ p’≤ m and p’= p, and a ≤ q’≤ b, where a = max{1, q − sp} and b = min{q + sp, n}, then (p’, q’) ∈R (Neighborhood constraint)
Our objective is to find R that maximizes the total weight ∑(p,q)∈rWp,q where each job is assigned to at most one crane and each crane is assigned to at most one job.
4.2 Algorithm Description
We follow the approach in section 3.2 here.
4.2.1 The Structure and Value of an Optimal Solution
We continue to consider the cranes one by one. For each crane cx, we attempt to assign every job jy(1 ≤ y ≤ n) to it and compute the total throughput up to this step to give a partial optimal solution Px,y.
Here, the partial optimal solution Px,y is cumulative and the edge inclusion (x, y) ∈ Rx,y may not hold. However, different from the definition used in the previous section, crane x must be assigned some job j (1 ≤ j ≤ y) for Px,y, i.e., there must be an edge (x, j) ∈Rx,y, where (1 ≤ j≤ y); if there is no job in the interval [1, y] that can be assigned to crane x, then Px,y= 0. Now, we define the value of the partial optimal solution Px,yfor the different cases:
1. If x = 1 and y = 1, P1,1＝W1,1
2. If x = 1 and y > 1, P1,y:= max{W1,y,P1,y-1}
3. If x > 1 and y = 1, Px,1=Wx,1
4. If x > 1 and y > 1, Px,y:= max{Px,y-1,P i,c +Wx,y}, 1 ≤ i < x, c = y− max{sx, si} − 1.
(1) is the basic case and (2) and (3) are the special cases. (2) has been explained in the previous section. (3) is different. Since we require for Px,ythat crane cxmust be assigned job jy, we have no choice but to assign this job to the current crane when there is only job available. The induction step in (4) is somewhat complex. In the first case, we keep job jyunassigned, so we are reduced to assigning cranes c1, c2, . . . , cx to jobs j1, j2, . . . , jy; hence, we obtain Px,y-1. In the second case, since we assigned job jyto crane cx, the Neighborhood constraint for cxmust be considered. Also, we must consider the Neighborhood constraint for the cranes c1, c2, . . . , cx which are assigned to jobs. The Non-crossing constraint simplifies the computation leaving us only to check the neighborhood constraint for the “largest label”crane assigned and is the reason the c value is needed in the formula.
The final optimal is the maximum value of all partial optimal solutions obtained, i.e., it is max{Px,y} over all (x, y), 1 ≤ x ≤ m, 1 ≤ y ≤ n.
4.2.2 A Proof of Optimal Substructure
Similar to the earlier problem, we show that this problem has an optimal substructure. As before, we use the fact that Px,y≥ Px,y’ if y ≥ y’(**). This is easy to verify since a partial optimal solution is cumulative for each crane x. As before, we have the following cases:
1. If x = 1 and y = 1, clearly P1,1= W1,1 is the optimal solution
2. If x = 1 and y > 1, only one crane is involved, so the Neighborhood constraint does not take the effect. The proof is then as given in the previous section
3. If x > 1 and y = 1, since crane cxhas to be assigned a job, and there is only one job, clearly Px,1 = Wx,1
4. If x > 1 and y > 1, Px,y= max{Px,y-1, Pi,c+ Wx,y}, 1 ≤ i < x, c = y−max{sx, si} − 1. We assume there is an optimal solution Px,y0> Px,y and the solution set corresponding to Px,y’ is R’x,y={(ca1, j b1), (ca2,j b2), . . . , (cak, j bk)}. Here, we can take this set to be ordered, i.e., a1≤ a2≤ . . . ≤ akand b1≤ b2≤ . . . ≤ bk, by virtue of the Non-crossing constraint. Noting ak= x from the definition above, there are now two possibilities for Px,y’ :
(a) If (x, y) ∈R’x,y, then Px,y’
-
会计师事务所任期与审计...
-
ADO.NET结构与概述英文文献和中文翻译
-
信息系统开发与数据库开...
-
机器人学入门力学与控制英文文献和中文翻译
-
园林植物景观的园林绿化...
-
桥式起重机智能防摆控制英文文献和中文翻译
-
起重机升降传感器系统英文文献和中文翻译
NFC协议物理层的软件实现+文献综述
江苏省某高中学生体质现状的调查研究
现代简约美式风格在室内家装中的运用
g-C3N4光催化剂的制备和光催化性能研究
高警觉工作人群的元情绪...
浅析中国古代宗法制度
巴金《激流三部曲》高觉新的悲剧命运
上市公司股权结构对经营绩效的影响研究
中国传统元素在游戏角色...
C++最短路径算法研究和程序设计