带有GDD假设的几类重新排序问题研究

发布时间：2017-11-30 18:26

  本文关键词：带有GDD假设的几类重新排序问题研究

  更多相关文章： 重新排序 gdd假设 错位限制 Parote最优 多项式时间 近似算法

【摘要】：重新排序(rescheduling)是人们非常关注的现代排序模型,它在制造业和服务行业中起着至关重要的作用.例如,在制造业中由于新订单的到达,订单的取消,订单优先顺序的改变,工件到达时间的改变,机器的故障等突发的错位使得我们不得不对还没有加工的工件进行重新排序.在对有新工件到达的重新排序研究中,Hall和Potts (2004)研究了在原始工件的序列错位和时间错位限制下的重新排序问题.本文的研究是在Hall和Potts工作的基础上考虑了在GDD(generalized due dates)假设下的重新排序问题,其中GDD假设指工期是按工件的完工顺序分配给工件的.我们研究的内容是按错位限制的不同,以及目标函数的不同,对由此产生的多个重新排序问题的计算复杂性进行分析.此外,我们还研究了相关的Pareto最优重新排序问题.本文的主要结果如下：·对于Γ∈{Dmax(π*),△max(π*)},γ∈{∑Tj,Lmax},重新排序问题1 | gdd,Γ≤k| γ在多项式时间O(n+nNlognN)内可解.·对于Γ=∑△j(π*),γ∈{∑Tj,Lmax},重新排序问题1| gdd,Γ≤k|γ和1 | gdd | γ+μΓ是强NP-困难的.·对于Γ∈{Dmax(π*),△max(π*)},γ∈{∑Tj,Lmax},重新排序问题1 | gdd |γ+μΓ在多项式时间O(nNlognN+nNno)内可解.·对于γ∈{∑Tj,Lmax},Pareto最优重新排序问题1| gdd |(Dmax(π*),γ)和1 | gdd |(△max(π*),γ)都在多项式时间O(nnN)内可解.·重新排序问题1 | gdd,△max(π)≤k | Lmax是强NP-困难的.但当假设所有的位置工期dj≤0,对于0≤j≤n均成立时,我们给出问题1| gdd,△max(π)≤k | Lmax的一个最好可能的多项式时间近似算法.·建立了重新排序问题1| gdd,rR,△max(π*)≤k | γ的若干性质.其中γ,∈ {∑Tj,Lmax)证明重新排序问题1| gdd,rR,△max(π)≤k | Lmax是强NP-困难的.证明重新排序问题1| gdd,rR,△max(π)≤k | ∑Tj在拟多项式时间O(n2PT)内可解.
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223

【共引文献】

中国期刊全文数据库 前10条

1 袁芬;谷云东;尘非;;关于模糊工期平行机调度问题的若干结果[J];北京师范大学学报(自然科学版);2006年03期

2 张忠文;李四海;;一类离散型多资源排序算法[J];长春大学学报;2009年12期

3 陈小林;任子亭;;误工工件个数最少的多目标排序问题(英文)[J];重庆工学院学报(自然科学版);2009年01期

4 李蒙;唐万梅;唐国春;;机器不同时开工平行机排序问题的原始阈值算法[J];重庆师范大学学报(自然科学版);2008年03期

5 唐国春;;误工排序问题的研究[J];重庆师范大学学报(自然科学版);2009年02期

6 彭洪洁;苏永英;唐国春;;部分工件必须不误工的误工排序问题[J];重庆师范大学学报(自然科学版);2009年02期

7 彭洪洁;唐国春;;两个多重目标排序问题的多项式时间算法[J];重庆师范大学学报(自然科学版);2010年02期

8 杨明明;张淑娟;韩翔凌;;具有学习效应的间歇批生产的单机排序问题[J];重庆师范大学学报(自然科学版);2011年03期

9 王松丽;赵玉芳;崔苗苗;;带有释放时间的半连续型批处理机调度问题[J];重庆师范大学学报(自然科学版);2012年02期

10 陈荣军;两机器自由作业稠密时间表的优势集研究[J];常州工学院学报;2005年01期

中国博士学位论文全文数据库 前10条

1 马英;考虑维护时间的机器调度问题研究[D];合肥工业大学;2010年

2 钟雪灵;带强制工期非正则目标函数的排序问题研究[D];暨南大学;2010年

3 柳春锋;工程项目中技能型员工调度问题研究[D];合肥工业大学;2011年

4 王磊;面向订单生产的供应链排序问题研究[D];暨南大学;2011年

5 丁国生;多代理竞争排序问题的研究[D];上海大学;2009年

6 白芳;民航发动机机群调度优化与视情维修决策方法研究[D];南京航空航天大学;2009年

7 郑斐峰;占线订单排序问题及其竞争策略研究[D];西安交通大学;2006年

8 付旭云;机队航空发动机维修规划及其关键技术研究[D];哈尔滨工业大学;2011年

9 杨名;若干流水作业排序问题的算法研究[D];华东理工大学;2011年

10 方阳;关于一些在线分批排序问题的研究[D];华东理工大学;2011年

中国硕士学位论文全文数据库 前10条

1 陈雯;模糊环境下基于协同进化的柔性车间调度方法研究[D];武汉理工大学;2010年

2 莫泽;几种加工时间为变数的单机排序问题[D];苏州大学;2010年

3 王迅娣;成组加工排序和供应链在线排序问题[D];曲阜师范大学;2010年

4 李岩;加工时间可控的分批排序问题[D];曲阜师范大学;2010年

5 武光华;可拒绝排序和两台同类机半在线排序问题[D];曲阜师范大学;2010年

6 朱洪利;供应链管理中的分批调度问题[D];曲阜师范大学;2010年

7 焦李超;单机双目标串行分批排序问题[D];曲阜师范大学;2010年

8 盛蓉;基于收视率预测的电视节目编排优化研究[D];复旦大学;2010年

9 王锦;集装箱调度问题的平行机排序算法研究[D];复旦大学;2010年

10 刘娟;基于云模型的改进PSO算法在差异工件单机批调度中的应用研究[D];中国科学技术大学;2010年

，

本文编号：1240105