带运输机的流水车间调度的最优算法

发布时间：2018-06-13 20:39

  本文选题：流水车间 + 完工时间　； 参考：《系统科学与数学》2017年03期

【摘要】：研究带运输时间的流水调度:在该问题中有两台机器A,B和一个运输机V,n个工件,工件需要先在机器A上加工然后在机器B上加工最后被运输机V运往目的地,而且运输机V最初停在机器B旁边.模型的目标是使所有工件都运往目的地的时间最短.文中给出了三种情况下的最优调度算法:i)A,B机器加工工件顺序给定时我们给出了线性时间的最优算法;ii)所有的工件加工时间在机器B上时间相等时我们给出了时间复杂度为O(nlogn)的最优算法;iii)机器B上工件最短加工时间大于等于机器A上工件最长加工时间时给出了时间复杂度为O(n~2)的最优算法.
[Abstract]:This paper studies the flow scheduling with transport time: in this problem, there are two machines AZB and one transporter VN n workpieces, the workpieces need to be processed on machine A and then processed on machine B before being transported to the destination by V, And the transport V initially stopped next to machine B. The goal of the model is to get all the artifacts to their destination in the shortest time. In this paper, we give the optimal scheduling algorithm in three cases, that is, the order of the workpieces processed by the machine, the order of the workpieces, and the optimal algorithm of the linear time.) when all the workpiece processing times are equal on the machine B, we give the time. When the shortest processing time of workpiece on machine B is greater than or equal to the longest processing time of workpiece on machine A, the optimal algorithm of time complexity is given.
【作者单位】： 大连理工大学软件学院;大连东软信息学院软件工程系;
【基金】：国家自然科学面上基金(11571060) 辽宁省自然科学基金(201602041)资助课题
【分类号】：O224;TB497

【相似文献】

相关期刊论文 前10条

1 何勇;二项群试的竞争算法[J];浙江大学学报(自然科学版);1994年04期

2 钟嵬,殷志文,娄娜;赶工问题的一个新的最优算法[J];复旦学报(自然科学版);2001年04期

3 王伟,张永山,王焕定,张薇敬;结构主动控制的一种瞬时最优算法[J];哈尔滨建筑大学学报;2000年03期

4 程贞敏;李洪兴;;允许中断的同速机调度问题的一个最优算法[J];北京师范大学学报(自然科学版);2008年05期

5 连广昌,朱顺荣;Gale-Shapley 匹配的推广[J];南京理工大学学报;1997年06期

6 徐贤浩马士华;基于顾客化大量生产模式的计划平准化模型的最优算法的研究[J];武汉科技大学学报(自然科学版);2000年02期

7 肖耀球;一类随机型Flow Shops模型及其算法[J];系统工程;2001年02期

8 粟塔山;吴翊;;参数化滤波器逼近问题的全局最优算法[J];国防科技大学学报;2006年06期

9 苑延华,蔡吉花,杜红;公交车调度的数学模型[J];大学数学;2003年05期

10 蒋迅;;线性算子的最优线性算法[J];北京师范大学学报(自然科学版);1989年02期

相关硕士学位论文 前4条

1 陈幸瑜;两台同类机极大化机器最小负载问题研究[D];浙江大学;2008年

2 柴幸;最小化最大加权完工时间的平行分批在线排序问题[D];郑州大学;2015年

3 邱言玲;工件加工中的排序博弈方法[D];西安电子科技大学;2014年

4 王玉艳;极小化总完工时间的带服务等级平行机在线排序问题[D];浙江理工大学;2017年

，

本文编号：2015341