CARP中一个与Pearn下限等价的新算法

<正> 有约束边运行问题(CARP),包括有约束中国邮递员问题(CCPP)在内,是近年来颇受关注的一个运筹管理问题,该问题通常定义如下:     

Johnson法则在成组加工排序中的推广

成组技术（Group Technology）是把工件分组进行加工,以提高生产效率的一种生产组织方法,本文把两台机器同序作业（同顺序流水作业）排序问题F2│perm│C_(max)的John-son法则推广到成组加工上,提出确定组与组之间顺序的最优法则,给出了这个问题成组加工的最优排法,并分析算法的计算复杂性。     

双目标优化排序问题1/r_j,UET/L_(max)∩C_(max)

本文首先证明排序问题１／ｒｊ／Ｃｍａｘ的“随手加工”法则，然后在此基础上对１／ｒｊ，ＵＥＴ／Ｌｍａｘ∩Ｃｍａｘ给出一个多项式最优化算法．     

双目标优化排序问题1／rj，UET／Lmax∩Cmax

本文首先证明排序问题1/rj/Cmax的“随手加工”法则，然后在此基础上对1/rj,UET/Lmax∩Cmax给出一个多项式最优化算法。     

加工时间依赖于机器的自由作业排序问题

1992年M．Dror提出工件的加工时间依赖于机器的排序问题（schedulingwithmachinedependentprocessingtimes），并研究以最大完工时间（makespan）和以总的完工时间为优化目标的两种这类排序问题．然而，M．Dror对以总的完工时间为优化目标提出的“最优算法”是错误的．本文用算例表明他提出的算法不是最优的，并在机器连续加工的条件下，把这个排序问题转化成指派问题（assignmentproblem），从而可以用匈牙利算法得到最优解．最后，我们提出几个尚未解决的问题，以期引起国内外同行进一步研究．