Evaluation and Optimization of Scheduling Operations with Uncertain Task Durations

摘要：供应链管理，以及随之而来的过程调度，正受到越来越多的关注。然而，目前调度模型的一个主要限制是它们本质上是确定性的。这些模型假设诸如处理时间、成本、设备可用性和产品需求等数据是已知的。在实践中，这些项目往往存在相当大的不确定性。这意味着从现有确定性模型预测的解决方案可能不是很有用。PI计划在确定性模型的基础上进行有意义的扩展，从而有效地处理不确定性。本项目关注多产品批量和连续工艺制造、新产品开发以及任务持续时间不确定的任何调度情况下出现的调度操作的评估。这些可能对应于不精确的处理时间、由于失败而必须重复处理的批次，以及可能执行也可能不执行的条件任务。PI计划研究一个很大程度上具有符号意义的过程，该过程包括将提议的调度转换为一个有向无环图，在这个图上，分段多项式分布被考虑为狄拉克函数。为了得到计划完成时间的概率分布函数，在所有路径上求多重积分，这需要在多面体上求解析积分。用图分解的方法对该积分进行降维。该程序应允许快速评估各种工艺调度问题中的不确定性。对直接搜索和数学规划两种优化方法，也规划了这种评价技术在优化方法中的集成。

Abstract - Grossmann - 9810182 Supply chain management, and consequently process scheduling, are receiving increased attention. A major limitation of present scheduling models, however, is that they are deterministic in nature. These models assume that data such as processing times, costs, availability of equipment, and product demands are known. In practice, it is often the case that there will be considerable uncertainty in these items. This means that solutions that are predicted from existing deterministic models may not be very useful. The PI plans to build upon deterministic model and extend them in a meaningful way, so as to effectively handle the uncertainties. This project is concerned with the evaluation of scheduling operations that arise in multiproduct batch and continuous process manufacturing, in new product development, and in any scheduling situation which exhibits uncertainties in the task duration. These could correspond to inexact process times, lots whose processing must be repeated due to failures, and conditional tasks that may or may not be performed. The PI plans to investigate a largely symbolic procedure that consists of translating a proposed schedule into a directed acyclic graph on which piecewise polynomial distributions are considered with Dirac delta functions. To obtain the probability distribution function of the completion time of the schedule, a multiple integral is evaluated over all paths, which requires analytical integration over a polytope. The dimensionality of this integral is reduced with graph decomposition methods. The procedure should allow fast evaluation of uncertainties in a large variety of process scheduling problems. The integration of this evaluation technique in optimization methods is also planned, for both direct search and mathematical programming methods.