一个有宽容交货期的生产调度问题算法

以优势准则构建一个分枝状精确算法,最小化一个存在共同宽容交货期单机调度(排序)问题的加权超前延误工件总数,分枝个数可减少50%.

有宽容交货期的加权超前延误工件数问题

研究加权超前延误工件数问题.在单机存在非限制性共同宽容交货期(common due window,CDW)条件下,给出一个动态规划算法及一个近似算法;对单机限制性CDW中的某个特殊情况,给出一个多项式时间算法;对两台平行机非限制性CDW情况,构建一个伪多项式时间动态规划算法,证明其是一般意义下的NP-hard问题.

货物装卸中带共同宽容期的排序问题

考虑货物装卸管理中船主和港口之间存在的如下相互制约关系:有n条货船于零时刻同时抵达码头,因而也希望在同一时段[d,D]内完成装卸货物.如某船的货物在D时刻后才装卸完,则船主会向港方索取赔偿;反之,如货物在d前完成装卸,则船主会向港方给付一定奖金.因此从港方来讲要适当考虑n条货船的装卸顺序,使得总费用最少.对于这一NP-困难的排序问题,本文给出了两个动态规划解法及其多项式可解的特例,并给出了一个分枝定界算法.