带有不可用区间批运输排序问题

《带有不可用区间批运输排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、全日制研究生√类教育硕士别同等学力硕士学位论文题目：带有不可用区间的批运输排序问题论文编号：专业名称：应用数学培养单位：数学与系统科学学院沈阳师范大学研究生处制带有不可用区间的批运输排序问题摘要在实际生产中，因机器在加工过程中发生故障或维修等原因会使机器在某一区间不可用；而且在真实环境中，生产商不可能对每个工件规定工期,相反,他们要预设一些日期,完工的工件应该在那时被交货。我们把同时交货的工件看做一批，交货日期称为批交货期。则批的加工时间依赖于这批中所有工件的加工时间，等于所有工件的加工时间之和；批的完工时间等于这批中最后一个工件的完工时间。同批中工

2、件的完工时间相同，都等于这批的完工时间。本文结合带有不可用区间和批运输的情况，在这个模型中，工件的完工时间不仅受不可用区间的限制还与它所在批有关，批交货期等于批的完工时间。因此，工件的流水时间等于该工件所在批的批交货期。而对于带有一般批交货期和提早惩罚的排序问题，本文分别讨论了所有工件的加工时间相同时，两个不同的目标函数的极小化问题。一个工件的提早等于交货期与完工时间的差。具体研究的内容概括如下：1.对于单机问题机器上的任意时间段为不可用区间的情况，本文讨论的是目标函数是极小化总流水时间及运输费用之和的问题。对于上述问题分析了最优解的性质，给出了拟多

3、项式时间的动态规划算法及算法的计算复杂性，并用具体的数值例子表明了算法的有效性。2.对于两台平行机问题，其中一台机器上的任意时间段为不可用区间的情况，本文讨论的是目标函数是极小化总流水时间及运输费用之和的问题。对于上述问题给出了最优解的性质，拟多项式的动态规划算法及算法的计算复杂性。3.对于恒速机问题，考虑其中一台机器上的某个时间段是不可用区间的情况，也讨论了目标函数是极小化总流水时间及运输费用之和的问题。给出了最优解的性质，拟多项式时间的动态规划算法。4.对于单机问题，考虑带有一般批交货日期和提早惩罚的排序问题，当所有工件的加工时间相同时，目标函数

4、分别为极小化最大提前惩罚与总拒绝工件的权和之和及极小化总加权提早与总拒绝工件的权和之和。针对这些问题进行了讨论，给出了最优解的性质及最优算法，并用数值例子进一步验证了此算法。关键词：不可用区间，批运输，批交货期，计算复杂性，动态规划算法BatchDeliverySchedulingProblemsWithUnavailabilityConstraintsAbstractIntherealindustrysettings,becauseofthebreakdownormaintenanceofthemachineduringtheprocessing,

5、themachineisunavailableinsomeinterval.Inrealenvironments,theproducersmaynotstipulatetheduedateforeachspecificjob;instead,theymusthavesomeprespecifieddatesatwhichthecompletedjobsshouldbedelivered.Weregardthejobsthataredeliveredsimultaneouslyasabatch,deliverydatesisnamedbatchdeli

6、verydates.Sothecompletiontimeofabatchupontheprocessingtimesofallthejobsinthebatch,isequaltothesumoftheprocessingtimesofallthejobsinthebatch.Thecompletiontimeofabatchisequaltothecompletiontimeofthelastjobinthebatch.Allthejobsinabatchhavethesamecompletiontimewhichisequaltothecomp

7、letiontimeofthebatch.Consideringunavailabilityconstraintsandbatchdeliveryinthispaper,thecompletiontimeofajobisnotonlyrelatedtounavailabilityconstraintsbutalsothebatchcontainingthejobinthismodel.Abatchdeliverydateisequaltothecompletiontimeofthebatch.Hencetheflowtimeofajobisequal

8、tobatchdeliverydateofthebatchcontainingit.Moreover,for