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

SGER：解决生产调度问题的分布式计算方法的实验研究

• 批准号: 9423694
• 负责人: Robert Davis
• 金额: $ 2.99万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-06-01 至 1996-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9423694&HistoricalAwards=false
• 关键词: SGER; Experimental; Investigation; Distributed; Computing

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.

小行星9423694 本研究探讨在分散控制制造环境下，利用平行演算法求解生产排程及其他相关问题的可行性与有效性。 在一个并行的分布式控制架构下，一个问题被划分并同时由几个处理器求解，每个处理器只贡献总求解时间的一部分。 一个混合整数规划制定的作业车间调度程序被用作一般模型结构的研究。 然后通过参数调整将模型转换为其他调度场景（例如，流水作业问题）。 重点是排列时间表。 一组排列时间表制定使用n元结构。 n叉树中的分支变量是序列中每个作业的位置。 这种结构是常见的许多分支和定界的解决方案排序和调度问题。 使用深度优先搜索规则，通过n叉树，所有的工作序列隐式评估，以解决问题。 将解决几个示例问题。 使用样本问题的结果，在分布式控制架构中的并行算法的行为将其特征在于在算法的解决方案的时间，通信开销，由于处理器之间的数据交换，以及其他算法的开销，由于启动，搜索，和风下来。 正如早期的研究已经建立的，实际规模的调度问题是非常计算密集型的，当留给一个单一的处理器，可以采取非常大量的时间来解决，特别是如果采用精确的解决方案。 并行编程在减少处理器上的计算负载以解决问题方面提供了一些承诺。 因此，在解决这类问题中获得的任何见解都将为经济的几个部门提供一些经济效益，因为在生活的几个领域都会遇到调度问题。 此外，还有其他几类问题，它们的行为与调度和排序问题相似。 如果在解决调度问题方面取得进展，这些类别的问题就会受益。