带有资源约束的两台机器流水作业排序问题

本文研究了带有资源约束的两台机器流水作业中的最小排序长度问题,并证明了[4,5]中提出的F2|pmtn、res 111|C_(max)是强NP—困难的。     

m台机器上流水作业时间表问题的复杂性及一种新的启发式算法

研究流水作业时间表问题，在具有延迟时间的条件下证明该问题是强NP-困难的．给出一种新的启发式算法，并证明该算法的最坏性能比是(m 1)/2，且上界是紧的．     

有序流水作业时间表问题是NP—困难的

讨论两台机器上的有序流水作业时间表问题，证明两台机器上的有序流水作业时间表问题是ＮＰ－困难的。     

一类两机器 no-wait 流水作业总完工时间问题

在两机器 no-wait 流水作业问题中,每个工件在加工前有一调整时间,加工完之后有一移走时间,同一工件的调整和移走是可以重叠的,但加工时间不能重叠,同时任一工件在第二台机器上的加工必须紧接在它在第一台机器上的加工之后进行,本文以总完工时间为目标函数,讨论问题最优解中工件排列应满足的条件;其次讨论当工件的三种时间满足一定条件时最优时间表的求法;最后为问题设计了一个近似算法.     

流水作业由二台柔性机器组成时的极小完工时间之和问题

该文考虑下述由2台机器组成的流水作业问题:n个相同工件需依相同次序在机器1、2上共进行3次加工.工件j的第一次加工在机器1上进行,所需时间为p1;其第二次加工或单独在机器1上或单独在机器2上进行,当工件j的第二次加工在机器1上进行时,所需时间为p12,当工件j的第二次加工在机器2上进行时,所需时间为p21;其第三次加工需在机器2上进行,所需时间为p2.要求适当安排这n个工件的加工方式以使它们的完工时间之和达到极小.对该问题作者对应不同情况给出了不同的最优解法.     

两类极小化最大加权完工时间排序问题研究

研究两个单机排序问题。目标函数均是最大加权完工时间。对于问题I｜｜maxw,c,证明了LW规则序是最优排序,而问题1｜r,｜maxw,cj．用3-划分问题归结。证明是强NP困难的。     

三台机器流水作业中存在不同调整时间的Ｌot—streaming问题

对三台机器流水作业的Ｌot-streaming问题（简称ＬＳ）以往的研究在忽略调整时间，分批数固定的条件下，寻找最优分批大小；本文对机器i每加工一个新的子批量分别引入一独立的调整时间si=kpi(i=1,2,3)，研究同时决定最优分批数及分批大小，并给出了相应最优算法。     

一种求解一类拟可微函数极小化问题的算法

本文对一类形如F(x)=g(x, (?)(x),…,(?)(x))+h(x)的拟可微函数(在Demyanov和Rubinov意义下),给出了一种优化算法,并证明了算法的收敛性。这里g,φ_(ij)分别为R~(m+n)和R~n上的连续可微函数,h(x)为R~n上的凸函数。     

A Modified Differential Evolution for Uniform Parallel Machines Scheduling Problem with Minimizing Makespan

The problem of scheduling jobs on uniform parallel machines with makespan (Cmax) minimization objective was studied.Due to its non-deterministic polynomial-time (N) hard nature,it is difficult to achie...     

集合覆盖问题的一种启发式算法

给出了完备策略的概念，并提出了一个求解集合覆盖问题的启发式算法，对该算法的合理性、时间复杂性以及精度进行了分析。用该方法可以求解其它的NP困难问题。     

柔性流水作业排序问题的贪心算法求解

柔性流水作业排序问题是一类复杂的车间作业调度问题。针对通常情况下调度问题求解困难的问题,给出了求解柔性流水作业排序问题近似解的贪心算法,并对其性能进行了分析测试。结果表明,虽然该贪心算法求出的近似解与最优解相比有一定误差,但由于其时间复杂度较小,因此对求解车间作业调度问题仍有一定的现实意义。     

转盘上单机排序问题的可解情形

文献［１］中证明，即使只有一台加工机器，带有转盘的流水作业问题的加工全长问题Ｔ１也是强ＮＰ困难的。本文讨论问题Ｔ１的几个多项式时间的可解情形     

一类装配式作业排序问题计算复杂性研究

探讨装配式作业排序问题的计算复杂性，证明了在优化指标为作业排序长度的条件下该问题是ＮＰ－完全问题。     

带运输时间的Flow-shop时间表问题

研究带运输时间的流水作业时间表问题，同一工件在一台机器上完工之后，在另一台机器上开始加工，且运输过程只能由机器R完成，证明在只有两台机器的情况下，该问题是强NP-困难的，并构造一个启发式算法，证明该算法的紧界为2。     

平行机上一种带拒绝费用的排序问题研究

主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是NP一难的证明。针对该排序问题给出了伪多项式时间的动态规划算法且设计出了FPTAS。     

基于Petri网和UML的流水作业调度模型设计及实现

为了对流水作业调度的行为提供支持,需要对其进行有效的建模和模型分析。Petri网具有坚实的理论基础和易于使用的图形表示,是一种理想的建模和分析工具。UML是一种易于编程实现的面向对象建模工具。针对UML和Petri网建模的特点,本文采用Petri网与UML相结合的建模分析方法,融合了Petri网精确、严格的形式化描述和UML友善的用户界面的优点。并提出了将Petri网转化为一种可以表示对象间的同步、并发的扩展状态图的方法。利用Petri网描述系统的动态特性,经过分析、验证或仿真后,通过提供的转化规则将Petri网模型转化成相应的UML动态图、扩展的状态图,对流水作业调度问题建模。利用动态规划算法解决满足Johnson法则的最优作业调度问题,并用Java实现。