SGER: An Experimental Investigation of Distributed Computing Approaches for Resolving Production Scheduling Problems

9423694戴维斯本研究探索了利用并行算法解决生产调度等相关问题的可行性和有效性，是一个分布式控制的制造环境。在并行分布式控制体系结构下，问题由多个处理器同时划分和解决，每个处理器只贡献总时间的一部分。采用作业车间调度规划的混合整数规划公式作为研究的一般模型结构。然后通过参数调整将模型转换为其他调度场景(例如，流水作业问题)。重点放在排列时间表上。使用n元结构来表示一组置换调度。N-ary树中的分支变量是序列中每个作业的位置。这种结构在排序和调度问题的许多分支和定界解决方案中是常见的。使用深度优先搜索规则遍历n-ary树，所有作业序列都被隐式评估以解决问题。将解决几个样本问题。使用样本问题的结果，分布式控制体系结构中的并行算法的行为将从算法求解时间、处理器之间的数据交换引起的通信开销以及由于启动、搜索和结束而产生的其他算法开销方面来表征。正如早先的研究已经确定的那样，实际规模的调度问题是非常计算密集的，当留给单个处理器时，可能需要非常大量的时间来解决，特别是在采用精确解的情况下。并行编程在减少处理器上的计算负载以解决问题方面提供了一些希望。因此，在解决这类问题方面获得的任何见解都将为经济的几个部门提供一些经济利益，因为在生活的几个领域都会遇到调度问题。此外，还有其他几类问题的行为类似于调度和排序问题。如果在解决调度问题方面取得进展，这类问题将会受益。

9423694 Davis This research explores the feasibility and the effectiveness of using parallel algorithms for solving production scheduling and other related problems is a distributed control manufacturing environment. Under a parallel, distributed control architecture, a problem is partitioned and solved simultaneously by several processors, with each processor contributing only a portion of the total time to the total solution time. A mixed integer programming formulation of the job shop scheduling program is used as the general model structure for the research. The model is then transformed through parameter adjustments into other scheduling scenarios (e.g., flow shop problem). The emphasis is on permutation schedules. A set of permutation schedules is formulated using an n-ary structure. The branching variable in the n-ary tree is the position of each job in the sequence. This structure is common to many branch and bound solutions for sequencing and scheduling problems. Using a depth first search rule through the n-ary tree, all job sequences are implicitly evaluated to solve the problem. Several sample problems will be solved. Using the results from the sample problems, the behavior of parallel algorithms in a distributed control architecture will be characterized in terms of algorithmic solution time, communication overhead due to data exchanges between processors, and other algorithmic overheads due to start up, search, and wind down. As earlier research has established, scheduling problems of practical sizes are very computationally intensive and when left to a single processor, can take an extremely large amount of time to solve, especially if exact solution approaches are employed. Parallel programming offers some promise in reducing the computational load on a processor to solve a problem. Therefore, any insights gained in solving this class of problem will offer some economic benefits to several sectors of the economy given that scheduling problems are encountered in several areas of life. In addition, there are several other classes of problems that behave alike and are similar to scheduling and sequencing problems. These classes of problems stand to gain if progress is made in solving scheduling problems.