具有维护活动的松弛工期调度问题研究

摘要

研究具有恶化和资源依赖性的维护活动与松弛工期的单机调度问题，其中工件的实际加工时间取决于工件是在维护活动之前还是之后进行加工的，工件的工期表示为其实际加工时间与松弛变量(即共同流量)之和。此问题的研究目的是确定工件的加工序列、维护活动所处的位置、松弛变量的大小以及维护活动所消耗的资源，以便其与提前、延迟完工时间和松弛变量的总成本达到最小。对于已知序列，求得松弛变量的值等于序列中某个位置工件的开始加工时间。通过分情况讨论维护活动的位置，将目标函数转化为分别只与工件加工顺序和只与资源有关的函数，然后将其转化为指派问题或利用向量匹配规则获得目标函数的最小值，最后给出了相应的算法，并证明此问题在多项式时间内可解。

关键词

调度 / 维护活动 / 松弛工期 / 单机 / 多项式时间

基金资助

辽宁省兴辽英才计划(XLYC2002017)