- 上一篇：残余应力状态的影响刀具寿命英文文献和中文翻译
- 下一篇：噪音工程齿轮模型英文文献和中文翻译
1. Non-crossing constraint: Cranes cannot cross over each other. This is a structural constraint on cranes and crane tracks.
2. Neighborhood constraint: There is a minimum distance between cranes. This arises, for example, since cranes require flexibility in space to perform jobs and/or for safety reasons. The effect of this constraint is that neighboring jobs may be affected and may not be assignable to other cranes.
3. Job-separation constraint: Certain jobs cannot be done simultaneously. For example, jobs bound for the same yard may require separation in time to avoid trailer congestion in lanes.
In the following sections, we first consider these constraints separately and then simultaneously. In section 3, an O(mn) dynamic programming (DP) algorithm is given to solve the problem with only the Non-crossing constraint where m is the number of cranes and n is the number of jobs. In section 4, we use an O(m2n) dynamic programming algorithm to achieve an optimal solution for the problem with both the Non-crossing and Neighborhood constraints. In section 5, assuming all three spatial constraints, we show the problem to be NP-complete and give two heuristic approaches to solve the problem — a probabilistic tabu search and a squeaky wheel optimization with local search method. In section 6, we provide experimental results and compare the different approaches.
3 Scheduling with the Non-Crossing Constraint
3.1 The Problem
Throughout this work, C= {c1, c2, . . . , cm} is a set of cranes and J= {j1, j2, . . . , jn} a set of jobs. The order of subscripts assigned to the cranes and jobs represents their spatial (assumed linear) distribution, i.e., the neighbor of j1is j2, the neighbors of j2are j1and j3,. . . , and the neighbor of jnis jn−1, The same holds for the cranes.
An m × n adjacency matrix, W , is used to represent the relationships between jobs and cranes. For each Wx,y∈W , the value Wx,y represents the throughput when job jy is assigned to crane cxwhere Wx,y= 0 if job jycannot be assigned to crane cx. The Wx,y values arise from the different job sizes and crane capacities.
We seek a solution set,R={(p, q )|1 ≤ p≤ m, 1≤q≤n, Wp,q> 0}, such that the following constraint is satisfied: For all (p1, q1), (p2, q2)∈R, p1< p2if and only if q1< q2. Viewing p’s and q’s, as subscripts in C and J respectively, we see that any crane-job assignment in R satisfies the Non-crossing Constraint.
The objective is then to find a set R which maximizes ∑(p,q)∈rWp,q subject to the constraints that each job is assigned to at most one crane and each crane is assigned to at most one job.
3.2 Algorithm Description
We now provide a dynamic programming (DP) approach and describe how to characterize an optimal solution. DP procedures for computing values of solutions in a bottom-up way and for constructing solutions from computed information are omitted since they follow directly and are required only in implementation.
3.2.1 The Structure and Value of an Optimal Solution
We consider the cranes one by one. For each crane cx, we assign every job jy(1 ≤ y ≤ n) to it and compute the total throughput to derive a partial optimal solution Px,ywhich denotes the optimal value up to the step we assign job jyto crane cx. Here, it is not necessary that job jyis actually assigned to crane cx, i.e., (x, y) ∈Rx,y may not hold, where Rx,yis the partial solution set corresponding to the partial optimal solution Px,y.
The following computes the partial optimal solution, Px,y, recursively, for 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’, P 1,y-1}
3. If x > 1 and y = 1, Px，1:= max{Wx,1, Px-1,1 }
-
会计师事务所任期与审计...
-
ADO.NET结构与概述英文文献和中文翻译
-
信息系统开发与数据库开...
-
机器人学入门力学与控制英文文献和中文翻译
-
园林植物景观的园林绿化...
-
桥式起重机智能防摆控制英文文献和中文翻译
-
起重机升降传感器系统英文文献和中文翻译
NFC协议物理层的软件实现+文献综述
江苏省某高中学生体质现状的调查研究
现代简约美式风格在室内家装中的运用
g-C3N4光催化剂的制备和光催化性能研究
高警觉工作人群的元情绪...
浅析中国古代宗法制度
巴金《激流三部曲》高觉新的悲剧命运
上市公司股权结构对经营绩效的影响研究
中国传统元素在游戏角色...
C++最短路径算法研究和程序设计