关于两类排序模型的若干结果

论文摘要

排序问题是指在一定的约束条件下考虑如何对工件和机器分配时间资源,从而使一个或多个目标达到最优。本文中主要研究了两类排序模型:（1）带有分批费用的单机平行分批排序问题;（2）具有相同工期的单机最小化加权总误工问题。（1）带有分批费用的单机平行分批排序问题我们研究的问题是在单机平行分批排序中将通常的正则目标函数加入分批费用。模型可以描述如下:假设有n个工件J1,J2,…,Jn,一台可以同时至多加工b个工件的批处理机。每个工件Jj具有加工时间pj。假设工件和批处理机都在零时刻到达。工件被成批地进行加工,并且一旦开始加工就不允许中断。每批的加工时间等于该批中工件的最大加工时间。目标函数为通常的正则函数与分批费用之和。用f表示一般的正则函数,V表示分批所产生的总的分批费用。以下假定每分一批产生的分批费用为v。若共分了m批,那么总的分批费用V=mv。我们的问题可以简记为1|p-batch,b=∞（b＜n）|f+V。我们采用动态规划的方法针对带有分批费用的不同目标函数的模型分别给出了其最优解的算法。（2）具有相同工期的单机最小化加权总误工问题尽管单机最小化加权总误工问题经常在实际中遇到,但由于对工期为任意值的研究比较困难,因此有关结果在文献中出现的却并不是很多。近来人们研究的兴趣越来越多地放在工期取特殊值的模型。例如,具有相同工期dj=d,工期等量松弛（SLK）dj=pj+q,其中q为给定的常数,以及更一般情形工时加等待工期（PPW）dj=αpj+q,其中α、q都为给定的常数。还有一些学者则关注了在其他参数上进行特殊限制的情形,如问题1|wj=1|∑wjTj,1|wj=kpj|∑wjTj,1|pj=p|∑wjTj在文献[11][5][8][10]中都有所研究。我们研究的问题1|dj=d|∑wjTj已知是一般意义下的NP-困难问题[9]。Lawler和Moore[7]对该问题给出了一个拟多项式时间算法。而问题1||∑wjTj是强NP-困难的[5][10]。Cheng等人[17]给出了此问题的O（n2）时间的近似算法。我们把该算法得到的目标值作为问题1|dj=d|∑wjTj的一个上界。类似于Cheng等人在[17]中对问题1|dj=pj+q|∑wjTj给出的算法,对问题1|dj=d|∑wjTj给出全多项式近似方案（FPTAS）。

论文目录

• 摘要
• Abstract
• 第一章 概述
• 1.1 排序的介绍
• 1.2 排序的记号
• 第二章 带有分批费用的单机平行分批排序问题
• 2.1 相关介绍
• 2.2 批容量无界情形
• 2.3 批容量有界情形
• 第三章 具有相同工期的单机最小化加权总误工问题
• 3.1 相关介绍
• 3.2 近似算法
• 进一步研究
• 参考文献
• 附录 硕士期间完成的论文
• 致谢