Zero-one quadratic programming algorithm for resource leveling of manufacturing process schedules
Zero-one quadratic programming algorithm for resource leveling of manufacturing process schedules
复制标题
用于制造流程调度资源均衡的零一二次规划算法
DOI：
10.1002/scj.4690261007
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Shigeru Okoshi
中科院分区：
文献类型：
--
作者：
M. Takamoto;Naoyuki Yamada;Yasuhiro Kobayashi;H. Nonaka;Shigeru Okoshi
在工业设备建设调度中，需要使波动或波动的最大峰值或日资源量的最大峰值最小化，该日资源量被计算为每个过程的日资源的总和。波动或最大峰值的最小化对应于使资源堆变平。为了执行这种资源均衡，我们需要确定一个目标函数，它是一个单调函数，简单地增加资源均衡的程度，然后通过固定的过程开始日期，同时最小化目标函数来解决优化问题。然而，工业厂房建设在许多情况下是一个大规模的调度，整个周期超过1000天，超过100个过程，因此很难获得全局优化解决方案。在这项研究中，我们开发了一种算法，解决了一个大规模的优化问题，以水平必要的资源。该算法能快速搜索到一个接近0-1二次规划问题全局最优解的好的次优解。该算法通过使用变量选择规则重复透视操作进行搜索，以实现资源均衡。我们将此算法应用于实际工厂建设进度的大规模调度，并在几分钟内成功地获得了一个实际的次优解（CPU功率：28 MIPS）。结果表明，该算法对大规模施工调度中的资源均衡问题具有实用价值。
In industrial plant construction scheduling, it is necessary to minimize the fluctuation or the maximum peak of the fluctuation or the maximum peak value of the daily resources amount, which is calculated as the sum of daily resources for each process. Minimization of the fluctuation or the maximum peak value corresponds to leveling the pile of resources. To perform this resource leveling, we need to decide on an objective function which is a monotone function that simply increases with the degree of resources leveling and then solve the optimization problem by fixing the process start dates while minimizing the objective function. Industrial plant construction is, however, in many cases a large-scale scheduling with an entire period of more than 1000 days and more than 100 processes, so it is very difficult to obtain a global optimization solution. In this study, we have developed an algorithm which solves a large-scale optimization problem to level necessary resources. This algorithm can quickly search for a good suboptimal solution close to the global optimal solution of a 0-1 quadratic programming problem. The algorithm searches by repeating a pivot operation using variable selection rules for resources leveling. We applied this algorithm to large-scale scheduling for an actual plant construction schedule, and successfully obtained a practical suboptimal solution within a few minutes (CPU power: 28MIPS). The results suggest that the algorithm is practical for resources leveling of large-scale construction scheduling.