菜单
  
    ≤ Pak,bk, since Pak,bk is the partial optimal solution. Hence, Px,y’≤ Px,bk, since ak= x. From property (**), we know Px,y-1 ≥ Px,bk since y − 1 ≥ bk(job jyis unassigned). So Px,y−1 ≥ Px,y’. By the recursive definition, Px,y≥ Px,y-1. Hence, we get Px,y≥ Px,y’, which contradicts the assumption Px,y’ > Px,y. So Px,y is the optimal solution in this case

    (b) If (x, y ) ∈ R’x,y, then Px,y’ ≤ Pak-1,bk-1+Wx,y, since Pak-1,bk-1 is the partial optimal solution. Obviously 1 ≤ ak-1<x, so we let i = ak-1 and c = y−max{sx, si} − 1. We know bk−1≤c since the cranes cxandciare both assigned jobs and their Neighborhood constraints are in effect. From (**), we get Pi,c≥ Pi,bk-1 because of c ≥ bk−1, i.e., Pak-1,c + Wx,y≥ Pak-1,bk-1,+Wx,y, and so  Pak-1,c+Wx,y≥Px,y’. From the definition Px,y= max{Px,y-1,Pi,c+Wx,y}, we know Px,y≥ Px,y’ , which contradicts the assumption Px,y’> Px,y. Hence, Px,y must be the optimal solution in this case

    We conclude that Px,y is the optimal solution for all (x, y), 1 ≤ x ≤ m, 1 ≤ y ≤ n.

    4.3  The Time Complexity of the Algorithm

    Since, for each partial solution Px,y, we take the maximum value of the partial solutions Pi,c, 1 ≤ i < x, the time complexity is O.

    5  Scheduling with the Job Separation Constraint

    5.1  The Problem

    We can now study the third and most general spatial constraint — the Job-separation constraint. An n × n matrix D represents this constraint: Dp,q= 1(1 ≤ i ≤ n, 1 ≤ j≤ n), when job jpand jq cannot be done simultaneously. Otherwise, the elements of D are 0. Note that D is symmetric. We seek a solution set R = {(p, q)|1 ≤ p ≤ m, 1 ≤ q ≤ n, Wp,q> 0}, for which the following three conditions are satisfied:

    1. For all (p1, q1), (p2, q2) ∈ R, p1< p2  if and only if q1< q2(Non-crossing constraint)

    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 = max{q + sp, n}, then (p’, q’) ∈R (Neighborhood constraint)

    3. For all (p, q) ∈R, if 1≤ p’≤ m, and Dq,q’= 1, then (p’, q’)∈R(Job-separation constraint)

    The objective is to find a set R which maximizes 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.

    5.2  Proof of NP-completeness

    To show that this problem is NP-complete, we use the Independent Set problem which is defined as follows: Given a graph G= (V, E) and a positive integer k≤ |V |, is there a V’⊆ V such that for all u, v ∈V’, the edge (u, v) is not in E and |V’| ≥ k?

    In order to prove that this problem is NP-hard, we transform an arbitrary instance of the Independent Set problem to the problem in polynomial time. Assuming there are n nodes in the graph G = (V, E) of the Independent Set problem, we construct the model with n cranes and n jobs where the only edges are (1, 1), (2, 2),..., (n, n), all with weight equal to 1. The Job-separation constraint matrix D is defined as follows: For all (x, y) ∈ E, Dx,y= 1, otherwise Dx,y= 0, 1 ≤ x, y ≤ n. The transformation is illustrated in Figure 5 and can be achieved in polynomial time.

    Now we show that the Independent Set problem has a solution of size k if and only if the problem has a solution with total profit k. First, if there are k independent nodes in graph G, there must be k jobs that do not, pairwise, conflict. Since we constructed n parallel edges with weight 1, the Non-crossing constraint and Neighborhood constraint do not have any effect here. Hence, we can use k cranes to do the k jobs without violating the Job-separation constraint with total profit k. If we now assume that there is a solution in this problem with profit k, there must be k

  1. 上一篇:残余应力状态的影响刀具寿命英文文献和中文翻译
  2. 下一篇:噪音工程齿轮模型英文文献和中文翻译
  1. 会计师事务所任期与审计...

  2. ADO.NET结构与概述英文文献和中文翻译

  3. 信息系统开发与数据库开...

  4. 机器人学入门力学与控制英文文献和中文翻译

  5. 园林植物景观的园林绿化...

  6. 桥式起重机智能防摆控制英文文献和中文翻译

  7. 起重机升降传感器系统英文文献和中文翻译

  8. NFC协议物理层的软件实现+文献综述

  9. 江苏省某高中学生体质现状的调查研究

  10. 现代简约美式风格在室内家装中的运用

  11. g-C3N4光催化剂的制备和光催化性能研究

  12. 高警觉工作人群的元情绪...

  13. 浅析中国古代宗法制度

  14. 巴金《激流三部曲》高觉新的悲剧命运

  15. 上市公司股权结构对经营绩效的影响研究

  16. 中国传统元素在游戏角色...

  17. C++最短路径算法研究和程序设计

  

About

优尔论文网手机版...

主页:http://www.youerw.com

关闭返回