极小化加权总完工时间的分批排序问题

本文讨论了分批排序中极小化加权总完工时间的两个问题.就所有工件的加工时间都相等这一特殊情况,分别给出两个算法,并证明了算法的最优性.

一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究

本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.

极小化加权完工时间和的Flowshop问题的算法(英文)

本文讨论了极小化加权完工时间和的Flowshop问题.我们给出了一个最坏情况误差界为m的启发式算法,对于m=2的情况,如果工件具有一致权因子,即pi<pj意味着wi≥wj,(i,j=1,2,…,n).最坏情况误差界为2β/α+β,其中α和β分别是全部工序加工时间的最小值和最大值.此外,分析了m=2的两种特殊情况,给出了多项式算法.

极小化总完工时间同型机分批排序问题的最优算法

本文讨论了两台批容量为无穷的同型机分批排序问题中,目标函数为极小化总完工时间的排序问题。提出了一个多项式时间的动态规划最优算法。并通过算例对该算法的运行过程加以说明。

基于遗传算法的试验计划总完工时间极小化模型设计与实现

伴随着物联网技术和大数据分析技术的兴起,越来越多的企业由传统制造业向智能化转型,以实现产业升级,而总完工时间极小化,尤其是复杂产品的总完工时间极小化,是制造企业生产计划编制中的重要环节。若能实现总完工时间极小化模型的准确建立,既能改善计划的准确性也可以大幅度提高检测业务的工作效率。本文提出的试验检测计划的总完工时间极小化方法,经算法实现后得到的试验检测方案能够有效的提高产品的试验检测效率,缩短产品的试验检测周期。经实例验证,有良好的应用效果。

具有周期维护的最小化加权总完工时间的平行机调度研究

针对具有周期维护的最小化加权总完工时间的平行机调度问题,首先证明了该调度问题是NP-难问题,并提出最优调度方案的4条性质。然后在WSPT规则的基础上结合工件在多机环境中的分配机制(JCT、MCT、BF)提出了WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法,其中ROPT算法为其他3个算法的最优输出。最后通过数值实验对4个算法进行性能分析,结果显示:WSPTJCT算法、WSPTBF算法以及ROPT算法的性能与最大加工时长pmax呈倒U型;工件个数n越大,WSPTJCT算法、WSPTMCT算法、WSPTBF算法以及ROPT算法的性能越好。

折扣加权总完工时间的调整时间可分离无等待Flow Shop排序问题

研究 3台机器调整时间可分离的无等待 Flow Shop排序问题 ,目标函数为极小化折扣加权总完工时间。对某些特殊情况 ,给出问题存在多项式最优算法的充分条件。在此条件下得到求解调整时间可分离的无等待 Flow Shop排序问题的分派规则。

一类无界的不相容工件族分批排序加权总完工时间问题

考虑极小化加权总完工时间的一类无界的不相容工件族分批排序问题,给出了最优排序的性质和算法,并加以证明.对工件有k个到达时间的情形,给出了一个复杂性为O(2^(k-1)nlogn)的启发式算法.

加权总完工时间有限的资源约束单机排序问题

讨论工件加工时间依赖于分配给它的一类资源,且加权总完工时间有限,目标函数为极小化资源总量的单机排序问题,对问题1,给出了一个有关最优解中最优资源使用的重要性质并利用该性质,对于bj=b,wj=w,aj=a这种特殊情况给出了最优算法.

加工时间相同的分族分批排序加权总完工时间问题

考虑极小化加权总完工时间的单机分族分批排序问题,给出了最优排序的性质和算法,并加以证明,对工件有k个到达时间的情形,给出了一个复杂性为的启发式算法。

折扣加权总完工时间问题的半在线排序算法

讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|r_j,p_(min)≤p_j≤p_(max)|∑w_j(1-e^(-βC_j)),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间p→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同p_(min)=p_(max)

一种极小化∑w_jC_j的分批排序问题的算法

讨论了单机分批排序问题中目标是极小化加权总完工时间的问题.对于所有工件的加工时间都相等的情况,分别对常数个到达时间和任意个到达时间的情况给出了两个最优算法,并给出了其算法复杂性.

加权总完工时间有限的受资源约束排序问题

研究 1 | pj=fj( uj) ,∑jwj Cj≤C| ∑juj 型受资源约束排序问题。针对问题中加工顺序确定的情况给出两个寻求其最优资源分配的算法 ;就 fj=f和 fj=b- ajuj。

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。

无等待Flowshop带折扣加权排序问题的最优算法

讨论了目标函数为带折扣的加权总完工时间的无等待Flowshop排序问题,对其中三种特殊情况给出了最优算法.第一种问题是机器满足单调递增优势关系,第二种问题是机器满足单调递减优势关系,第三种是机器满足先递增、后递减的优势关系.

工件加工时间为非线性分段函数的单机排序问题

讨论工件加工时间是开工时间非线性分段函数的单机排序问题,目标函数为极小化最大完工时间,总完工时间和加权总完工时间.对于目标函数为极小化最大完工时间和总完工时间的问题,给出了求解最优排序的多项式算法,对于目标函数为加权总完工时间的问题,给出了工件间的一致关系.

一类加工时间依赖资源的单机成组排序问题

研究了加工时间依赖资源的成组排序问题.在这类问题中,加工时间是资源的线性函数,工件被分成若干个组,同组内的工件需连续加工,不允许分开,各工件组有固定的安装时间,目标函数为极小化加权总完工时间.针对这类问题构造了一个有效的下降算法.

基于加权总完工时间的两人合作排序博弈

现实活动中,往往存在一方无法独自完成一个项目中全部工件加工任务的情况,这就需要双方或者多方合作共同完成任务。假设每人有一台用于加工工件的机器,通过确定这批工件的一个恰当划分,把工件分配给两台机器,使得双方合作收益最大。本文研究当工件加工时间是其开工时间线性恶化函数,以最小的加权总完工时间作为加工成本,建立两人合作排序博弈模型。通过运用Matlab软件,分析不同的盈利能力和机会成本对最优解的影响,并与以总完工时间作为加工成本的模型进行比较,表明本文模型在盈利能力不强以及恶化因子小的情况下都可以求得最优解。

具有学习效应的两个单机排序问题(英文)

研究工件具有学习效应的两个单机排序问题.工件的学习效应指的是工件的加工时间为所排位置的函数.对以下两个目标函数:加权总完工时间与最大延误,证明在某些特殊情况下加权最小加工时间优先(WSPT)规则和最早工期优先(EDD)规则可以分别给出最优算法.也给出了这两个规则在一般条件下的最坏情况界.