限位排序和单机工件运输排序的若干结果

论文摘要

在本文中,我们研究了两种排序模型:（1）工件具有位置约束的限位排序问题。（2）工件先加工后运送到顾客的单机排序问题。 （1）工件具有位置约束的限位排序问题。 在限位排序中[1,6],我们有n个工件了J1,J2,…,Jn和m个工件族F1,F2,…,Fm且Fi∩Fj=Φ（i=j）,它们是工件集{J1,J2,…,Jn}的一个划分。每个工件Jj有一个加工时间pj,权wj,到达时间rj和一个工期真dj,每个族Fk有一个位置允许集Sk（?）{1,2,…,n},k=1,2,…,m.对于i≠j来说,Si与Sj可以相交。在文献中,这个问题被记为1|PR|f,其中f=Cmax,∑Cj,∑wjTj,∑wjUj,∑wjCj。 这个问题（1|PR|f）最早由林诒勋和原晋江提出,我们知道1‖∑wjCj可以按照Smith’s规则获得最优解,1‖Lmax可以按照EDD规则获得最优解,1‖∑wjUj和1‖∑wjTj都是NP困难的。但是1|PR|f∑wjCj的复杂性仍是未知的。我们通过考虑此问题的特殊情形,给出了一些多项式可解的例子,接着考虑了一个关于平行机排序问题。 （2）工件先分批加工后运送到顾客的单机排序问题。 在一般的单机排序和工件运输问题模型中,我们有n个工件J1,J2,…,Jn,它们先分批后在一台机器上加工,然后被一个有容量限制的汽车运送给两个顾客。每个工件Jj有一个加工时间pj/和一个尺寸sj,在这里sj代表工件Jj被装到汽车中所要占的空间大小。仅仅有一辆汽车去运送所有的工件,它有一个容量限制z。目标是寻找一个工件加工和运输的排序,使得所有工件被加工完毕并运送给顾客的时间达到最小。本文考虑的是在2T1≥T3限制下的问题。根据Lee和Chen[15]的记号,这个问题被记为1→D,k=2|v=1,c=z,2T1≥T3|Cmax,这里“1→D,k=2”表示工件首先在一台机器上加工,然后被运送给两个顾客;“v=1,c=Z”表示仅仅有一辆汽车去运送所有的工件,并且汽车的容量为z。 工件加工和运输的排序问题已经成为在近十几年里最重要的、被广泛研究的课题之一。Ahmadi[7]等人研究了两台机器（一台单机和一台随后的分批加工机器）的flowshop排序问题,目标是最小化最大完工时间与完工时间总和。Herrmann和Lee[14],Yuan[19],Chen[9]Yang[18]和Cheng[11]等人考虑了带有工期相关指标的分批排序问题。Lee和Chen[15]根据运输时间和汽车容量,而不管运送费用,考虑了另一种工件加工和运输的最小化最大完工时间问题。Chang和Lee[10]又发展了这个问题,他们考虑每个工件在汽车占据不同的空间。他们证明了这个问题1→D,k=2|v=1,c=z|Cmax是强NP-困难的,同时提供了一个启发式算法,它的最劣性能比为2。在2T1≥T3限制下,我们提供了一个最劣性能比为27/14的改进算法。

论文目录

• 第一章 排序问题概述
• §1.1 排序问题介绍
• §1.2 排序论记号
• 第二章 限位排序的一些结果
• §2.1 引言
• §2.2 一些多项式可解的例子
• §2.3 一个平行机问题
• 1≥T₃|C_max'>第三章 单机工件运输排序1→D,k=2|v=1,c=z,2T₁≥T₃|C_max
• §3.1 引言
• §3.2 启发式算法
• 结束语
• 参考文献
• 附录
• 致谢