学位论文之加工时间依赖开工时间的排序问题(pdf 39页)

学位论文之加工时间依赖开工时间的排序问题内容提要：
背景：
掉序(schedding)N题是一类重要的组合最优化问题，它产生的背景早期是机器
制造，后来被广泛用于计算机系统、运输调度、生产管理等领域。事实上，捧序
问题在编制作业计划、企业管理、航空航天、医疗卫生等各个领域都有着广泛的
应用．它是利用一些处理机(processor)或机器(埘achine)以及可能的资源(reso珊ce)，
“最优地”完成一些给定的任务(task)或工件(iob)。在处理这些任务(或工件)时还
需满足某些限制条件，如任务可以有就绪时间、完工可以有时限、任务的加工可
以有顺序关系(如出树等)、加工时间可以受资源的影响等。最优地完成指的是使目
标函数达到最小。目标函数通常是对加工时闻的长短、处理机的利用率等的描述。
恶化排,亭(deteriorating scheduling)f司题是一类重要的新型现代捧序问题。在这
类问题中，工件的加工时间不为常数，而是开工时间的函数，且通常是开工时间的
增函数。这类问题产生的背景有，如：在银铁企业中，某些工件的加工有温度的
要求，在满足温度要求的情况下，工件的加工时间是常数；如果工件在加工前有等
待时间，将引起温度的下降，这样一来，无论是重新加温使其满足温度要求还是
直接在低湿下加工情况，都将导致加工时间的增加。这类问题模型在维修工作方
面、塑料工业及医疗等领域也有广泛的应用。
..............................