由两台柔性机器组成的流水作业问题 被引量：1

1

作者 王景侠 孙世杰 《上海大学学报（自然科学版）》 CAS CSCD 2001年第3期218-220,共3页

研究了由两台柔性机器所组成的流水作业问题 ,其中有 n个相同工件 ,每一工件需先在机器 1上完成所需时间为 p1 的第一次加工 ,然后需单独在机器 1上或单独在机器 2上完成所需时间分别为 p1 2 、p2 1 的第二次加工 ,最后在机器 2上完成... 研究了由两台柔性机器所组成的流水作业问题 ,其中有 n个相同工件 ,每一工件需先在机器 1上完成所需时间为 p1 的第一次加工 ,然后需单独在机器 1上或单独在机器 2上完成所需时间分别为 p1 2 、p2 1 的第二次加工 ,最后在机器 2上完成所需时间为 p2 的第三次加工 .要求适当安排这 n个工件的加工方式和次序以使加工全程 (Cmax)最小 .本文对此问题给出了分析解 . 展开更多

关键词 排序 柔性机理 加工全程 流水作业问题 加工方式 加工次序 最优序

下载PDF 职称材料

带精确时间延迟的两台机流水作业问题研究 被引量：1

2

作者 王焕男 《黑龙江科学》 2020年第2期6-10,13,共6页

主要研究带精确时间延迟的两台机流水作业问题。每个工件Jj(j=1,2,…,n)有两道工序aj、bj,第一道工序先于第二道工序加工,第一道工序的完工时间caj与第二道工序的开始时间sbj之间存在一个精确时间延迟exact lj,即sbj=caj+lj。所有工序... 主要研究带精确时间延迟的两台机流水作业问题。每个工件Jj(j=1,2,…,n)有两道工序aj、bj,第一道工序先于第二道工序加工,第一道工序的完工时间caj与第二道工序的开始时间sbj之间存在一个精确时间延迟exact lj,即sbj=caj+lj。所有工序操作时间都相等aj=bj=a(j=1,2,…,n),且精确时间延迟是工序操作时间的整数倍lj=ka(k∈N+)。第一道工序在第一台机器上执行,第二道工序在第二台机器上执行,分别以极小化加权总完工时间、最大延误时间和总延误数为目标函数设计了最优算法。 展开更多

关键词 精确时间延迟 两台机 流水作业问题

下载PDF 职称材料

带广义偏序约束的Flow-Shop排序问题

3

作者 杜东雷 韩继业 《应用数学学报》 CSCD 北大核心 1997年第4期587-592,共6页

本文研究了一种新的排序问题:带‘广义偏序”约束的flow-shop排序问题.如工件Jj与工件.。之间有广义偏序,则Jj→Jk,且Jj的完工时间与Jk的开工时间的间隔不小于ljk和不大于ujk,0ljkujk.问题的目标函数是最大完工时间.我们证明了:具有比... 本文研究了一种新的排序问题:带‘广义偏序”约束的flow-shop排序问题.如工件Jj与工件.。之间有广义偏序,则Jj→Jk,且Jj的完工时间与Jk的开工时间的间隔不小于ljk和不大于ujk,0ljkujk.问题的目标函数是最大完工时间.我们证明了:具有比较简单的广义偏序约束的两台机器的flow-shop问题亦是NP-hard.我们给出了相应的启发式算法.对于单位加工时间,证明了一种较复杂的广义偏序约束的flow-shop问题是多项式可解的. 展开更多

关键词 Folw-shop排序 广义偏序 排序 流水作业问题

原文传递

三机流水作业问题若干特殊情形的NP困难性(英文) 被引量：2

4

作者 刘朝晖 俞文魮 《运筹学学报》 CSCD 2000年第1期43-49,共7页

本文研究以加工总长为目标函数的三台机器流水作业问题的特殊情形的计算复杂性，证明了下列情形为ＮＰ困难的：所有工件在第二台机器上有相同的加工时间；所有工件在第一和第三台机器上有相同的加工时间；每个工件至少有一个零工序；每... 本文研究以加工总长为目标函数的三台机器流水作业问题的特殊情形的计算复杂性，证明了下列情形为ＮＰ困难的：所有工件在第二台机器上有相同的加工时间；所有工件在第一和第三台机器上有相同的加工时间；每个工件至少有一个零工序；每个工件有一个丢失的工序。 展开更多

关键词 时间表 加工时间 NP困难性 三机流水作业问题

下载PDF 职称材料

多工作日历下流水作业调度遗传优化方法 被引量：3

5

作者 曾强 邓敬源 +1 位作者 张进春 沈玲 《计算机工程与应用》 CSCD 北大核心 2019年第4期238-247,共10页

针对多工作日历下的流水作业调度问题,提出了一种遗传优化方法。首先,提出了基于多工作日历的时间推算方法,解决了多工作日历下流水作业调度的关键问题:以Excel为平台设计了"工作制"工作表和"设备"工作表,在"... 针对多工作日历下的流水作业调度问题,提出了一种遗传优化方法。首先,提出了基于多工作日历的时间推算方法,解决了多工作日历下流水作业调度的关键问题:以Excel为平台设计了"工作制"工作表和"设备"工作表,在"设备"工作表中为每台设备指定工作制并设定工作时段;在此基础上,以Excel VBA为平台设计了5个基于工作日历的时间推算函数。其次,以Excel VBA为平台设计了遗传算法用于求解问题:个体采用整数编码方式,交叉操作采用"交换交叉"方式,变异操作采用"交换变异"方式,解码过程采用基于多工作日历的时间推算方法准确计算各工序开工和完工时刻。最后,通过案例分析验证了所提方法的有效性。 展开更多

关键词 流水作业调度问题 遗传算法 多工作日历 时间推算方法

下载PDF 职称材料

流水作业排序问题的启发式算法 被引量：1

6

作者 时凌 徐春 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2010年第5期13-15,共3页

研究了n个工件在2台机器下的流水作业排序问题,目标是使加权完工时间最小.同一工件在一台机器上完工后与在另一台机器上开工前存在一定的时间间隔,将其定义为运输时间,所有运输过程均由单自动机完成.讨论了该排序问题的复杂性,并引入了... 研究了n个工件在2台机器下的流水作业排序问题,目标是使加权完工时间最小.同一工件在一台机器上完工后与在另一台机器上开工前存在一定的时间间隔,将其定义为运输时间,所有运输过程均由单自动机完成.讨论了该排序问题的复杂性,并引入了一种启发式算法,证明了该问题是强NP困难的,该算法的紧界为3/2. 展开更多

关键词 流水作业排序问题 复杂性 启发式算法 运输时间 自动机

原文传递

使总完工时间达到最小的流水作业排序问题 被引量：2

7

作者 时凌 龙彩燕 张琼 《西南民族大学学报（自然科学版）》 CAS 2020年第6期638-642,共5页

研究带单服务器且服务时间相等的流水作业排序问题,该流水作业排序问题的目标函数是使总完工时间达到最小.利用目标和的数字匹配这个强NP-困难问题到带单服务器且服务时间相等的流水作业排序问题的归约,证明带单服务器且服务时间相等的... 研究带单服务器且服务时间相等的流水作业排序问题,该流水作业排序问题的目标函数是使总完工时间达到最小.利用目标和的数字匹配这个强NP-困难问题到带单服务器且服务时间相等的流水作业排序问题的归约,证明带单服务器且服务时间相等的流水作业排序问题问题也是强NP-困难的.引入加工顺序为最小加工时间优先的新启发式算法,并证明该启发式算法的上界是6/5,且该上界是紧的. 展开更多

关键词 总完工时间 流水作业排序问题 最坏性能比 单服务器

下载PDF 职称材料

带单机器人的流水作业排序问题的复杂性 被引量：1

8

作者 时凌 张琼 龙彩燕 《内蒙古民族大学学报（自然科学版）》 2021年第6期461-464,共4页

研究n个工件在2台机器上加工的流水作业排序问题,目标函数是使完工时间达到最小.当一个工件在一台机器上完工后到下一台机器上加工之前的时间间隔,称之为运输时间的时间间隔,所有运输均由单运输机来完成,机器人在同一时间只运输一个工件... 研究n个工件在2台机器上加工的流水作业排序问题,目标函数是使完工时间达到最小.当一个工件在一台机器上完工后到下一台机器上加工之前的时间间隔,称之为运输时间的时间间隔,所有运输均由单运输机来完成,机器人在同一时间只运输一个工件,证明对于这种特殊的排序问题仍然是强NP-困难的. 展开更多

关键词 流水作业排序问题 复杂性 单机器人

下载PDF 职称材料

带运输时间和单自动机的流水作业排序 被引量：1

9

作者 时凌 张琼 +1 位作者 时义梅 刘丁酉 《石河子大学学报（自然科学版）》 CAS 北大核心 2018年第4期524-528,共5页

本文研究n个工件在2台机器上加工的流水作业排序问题。同一工件在一台机器上完工后在下一台机器加工之前有一个时间间隔即运输时间,所有运输时间都是由单自动机来完成运输,同一时间自动机只能运输一个工件,本文主要研究所有加工时间均... 本文研究n个工件在2台机器上加工的流水作业排序问题。同一工件在一台机器上完工后在下一台机器加工之前有一个时间间隔即运输时间,所有运输时间都是由单自动机来完成运输,同一时间自动机只能运输一个工件,本文主要研究所有加工时间均匀等于1的情况下该问题的复杂性,并给出新的启发式算法,证明该算法的最坏性能比是3/2,且上界是紧的。 展开更多

关键词 流水作业排序问题 复杂性 运输时间 单自动机

下载PDF 职称材料

带服务器的3台机器流水作业排序启发式算法

10

作者 时凌 《武汉大学学报（工学版）》 CAS CSCD 北大核心 2007年第3期123-126,共4页

研究了带服务器的流水作业排序问题的复杂性和启发式算法.每个工件在机器上加工之前,必须由服务器先进行安装,在任何时刻服务器只能在1台机器上安装工件,目标是使最大加工时间达到最小.在只有3台机器的情况下,利用3-划分到该问题的一个... 研究了带服务器的流水作业排序问题的复杂性和启发式算法.每个工件在机器上加工之前,必须由服务器先进行安装,在任何时刻服务器只能在1台机器上安装工件,目标是使最大加工时间达到最小.在只有3台机器的情况下,利用3-划分到该问题的一个归约来证明该流水作业排序问题仍然是强-困难的.为此,引入一个新的启发式算法,并证明该启发式算法的紧界为2. 展开更多

关键词 流水作业排序问题 服务器 复杂性 启发式算法

下载PDF 职称材料

带运输时间和自动机的流水作业排序问题的复杂性 被引量：1

11

作者 时凌 文军 《数学物理学报（A辑）》 CSCD 北大核心 2008年第5期967-970,共4页

研究目标函数为使最大完工时间达到最小的三台机器情况下的流水作业排序问题,同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内,存在称为运输时间的时间间隔,所有的运输工作均由自动机来完成,自动机在同一时间内最多运输... 研究目标函数为使最大完工时间达到最小的三台机器情况下的流水作业排序问题,同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内,存在称为运输时间的时间间隔,所有的运输工作均由自动机来完成,自动机在同一时间内最多运输一个工件,文章研究该问题及其特殊情况下的复杂性. 展开更多

关键词 流水作业排序问题 运输时间 自动机 复杂性

下载PDF 职称材料

带单服务器的流水作业排序问题的复杂性

12

作者 时凌 张琼 龙彩燕 《延边大学学报（自然科学版）》 CAS 2022年第4期332-335,共4页

研究了一个带单服务器且加工时间相等的两机流水作业排序问题,其目标函数是使总完工时间达到最小.研究表明,该流水作业排序问题是强NP-困难的.针对该流水作业排序问题构造了一种新的加工顺序,并证明该加工顺序的紧界为7/6.

关键词 流水作业排序问题 总完工时间 单服务器 最坏性能比

下载PDF 职称材料

一种可控的两台机流水作业排序问题 被引量：1

13

作者 闻振卫 《数学的实践与认识》 CSCD 北大核心 2011年第22期134-139,共6页

在经典的两台机流水作业排序问题F_2‖C_(max)的基础上进行修改,将工件J_j在两台机上的加工时间由常数A_j和B_j改成A_j(x)=a_j+c_jx和B_j(x)=b_j-d_jx,其中x是某区间上的可控(决策)变量.排序的目标是,选择适当的x(对应相应的加工时间是A... 在经典的两台机流水作业排序问题F_2‖C_(max)的基础上进行修改,将工件J_j在两台机上的加工时间由常数A_j和B_j改成A_j(x)=a_j+c_jx和B_j(x)=b_j-d_jx,其中x是某区间上的可控(决策)变量.排序的目标是,选择适当的x(对应相应的加工时间是A_j(x)、B_j(x))(j=1,2,…,n)及相应的工件的加工顺序σ=[σ(1),σ(2),…,σ(n)],使时间表长(即最后一个工件J_σ(n)在第二台机上的完工时间)G_(max达到最小.给出了解决问题的有效方法. 展开更多

关键词 运筹学 生产管理 两台机流水作业排序问题 Johnson规则

原文传递