论文部分内容阅读
机器调度问题来源于不同的领域,如柔性制造系统、生产计划、计算机设计、后勤及通信等,这些问题的共同特性是没有一个有效的算法能在多项式时间内求出最优解。古典的作业车间问题(JobShopProblem,JSP)是最著名的机器调度问题之一。在过去的40年里,机器调度问题吸引了无数研究者的浓厚兴趣,大量的研究成果相继问世,但是对于调度问题的研究一般都在于静态调度问题的研究。可是在实际世界中调度很少是静态的,在调度执行过程中一些事件的发生往往是不可预测的,而一些事件的不可预测往往引起的是时间的不确定。
本文研究了具有时间不确定性的的作业车间问题,以古典的作业车间问题为背景,加入处理时间不确定性因素——处理时间在一个闭区间的范围内变化。为了求解含有该类不确定性时间因素的作业车间问题,我们以确定性车间调度问题的求解为基础,对一个确定性的作业车间问题进行分离逻辑(DifferenceLogic)建模,使用分离逻辑求解器求出一个近似最优的调度结果,在调度执行过程中使用插空策略(Hole-FillingStrategy),在每个作业处理结束时,根据该调度策略动态地调整调度方案,缩短生产时间。并通过实验证明了利用分离逻辑求解确定性的作业车间问题的有效性,同时也证明了在一般情况下使用插空策略动态调整调度结果可以有效地缩短调度执行时间。所有的测试结果是在1.8GHz的Pentium4处理器,512兆内存的硬件环境和LinuxRedHat9的软件环境下取得的。