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

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

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

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

准时生产和宽容交货中的排序问题

本文综述了近年来国内外对宽容交货中排序问题的研究．

宽容交货加权超前延误单机排序问题

该文研究下述宽容交货加权超前延误排序问题:n个工件具有一共同的宽容交货期,任一工件在宽容交货期内完工不受罚,超前或延误则受罚,惩罚系数依赖于工件.排序目标是找一个最优序和最优宽容交货区间位置使最小化加权超前延误惩罚之和.证明它是NP Completeness的,并给出一伪多项式算法,从而获知所研究问题是一般意义下NP Completeness的,也使该类问题的复杂性界限更清楚.

工件存在不同交货宽容期的最大加权超前延误问题

本文考虑下述排序问题：有ｎ个工件需在同一台机器上加工，对各工件有一 定容交货期．若一工件在其宽容期前完工则受加权超前惩罚，若在其宽容期后完工则受 加权延误惩罚．要求适当安排一加工方式使最大惩罚最小．文中相应某指定工件需准时 完工的上述问题征得了Ｎｐ－ｈａｒｄ性，给出了最优算法，并作了一些讨论．

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

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