非对称模糊加工时间工期指派调度优化问题的一类多项式求解算法

针对工件加工时间为非对称模糊数,极小化提前完工惩罚和拖期完工惩罚之和的均值的单机工期指派调度优化问题展开研究.证明了当模糊加工时间具有相同宽度比时,该问题是多项式可解的,并 给出了多项式求解算法.同时根据历史数据,构造了工期指派问题的调度模型,并利用所给出的算法求得最优解,从而 表明所提出的模型和算法的有效性.      

加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

加工时间依赖工件位置的树约束单机排序问题

讨论了工件的加工时间依赖于工件位置的树约束单机排序问题,给出了目标函数为最大完工时间的多项式算法.结果表明,最大家庭树中的工件优先于其它家庭树中的工件加工,并且其工件要连续加工所得到的排序为最优排序.     

加工时间可控的单机排序问题

研究带有学习效应和恶化效应的单机排序问题。在此模型中,工件的学习效应是与工件加工位置相关的减函数,工件的恶化效应是与其开始加工时间相关的线性函数。在无资源约束的情况下,分别讨论了目标函数为最大完工时间、总完工时间及总完工时间的绝对差之和的排序问题,证明了这些问题都是多项式时间可解的。对于带有资源约束问题,若分配一定的资源,工件加工时间会减少。讨论了在线性资源分配情况下,带有学习效应、恶化效应和资源分配量的交货期排序问题,其中所有工件有一个共同的交货期。目的是确定最优交货期、资源分配及工件的加工顺序,使交货期、提前、延误和资源分配量之和最小,通过将其转化为指派问题,证明问题是多项式时间可解的。     

工件可拒绝平行机排序

考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.如果拒绝一个工件,要花费一定的惩罚费用;如果接受这个工件,在m台机器中的一台上分批加工,定义一批的加工时间为这批中所包含的最长工件的加工时间.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的数时,给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案.     

带有学习效应和加工时间可控的排序问题

考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。     

加工时间依赖工件位置的链约束单机排序问题

讨论了工件加工时间依赖工件位置的链约束单机排序问题．对于链可中断和不可中断两种情形．证明了目标函数为最大完工时间和总完工时间时该问题仍然多项式时间可解．     

序列错位下完工时间和的随机重新排序问题

讨论了工件加工时间服从任意分布的随机重新排序问题,目标是使期望总完工时间最小.根据理论分析的方法,研究了工件的最优加工顺序.结果表明最短期望加工时间优先规则是使目标达到最小的策略,并由该策略得出多项式时间算法.     

带有学习效应和退化效应的加工时间与资源有关的单机排序问题

研究了同时带有学习效应和退化效应的加工时间与资源有关的多窗口单机排序问题。工件实际的加工时间是关于分配资源量的凸函数,并且是关于开始加工时间的线性递增函数。每个工件都有一个交货期的窗口。若工件在此窗口中完工,则不会产生惩罚费用;否则工件在此窗口之前或之后完工,则会产生相应的提前或延误费用。目标是确定工件最优的加工顺序和最优的资源分配量,从而极小化总费用函数。考虑两个问题,第一个问题的目标函数是与提前、延误工件数、窗口的开始时间、窗口的大小、资源分配量以及最大完工时间有关的函数;第二个问题的目标函数是关于提前、延误、窗口的开始时间、窗口的大小、资源分配量以及最大完工时间的函数。针对这两个问题也分别给出了两个多项式时间算法。
     

加工时间服从均匀分布的单机随机排序问题

讨论了工件的加工时间服从均匀分布的单机随机调度问题,目标是使拖后工件数的数学期望最小.采用理论分析的方法,研究了工件的最优加工顺序.结果表明:在(1)工件的权重相等(2)工件的权重与工件的平均加工时间成比例的两种情况下,最短期望加工时间优先规则的不可中断静态优先策略和不可中断动态优先策略是确定使拖后工件数最少的优先策略,并对算法的最优性进行了证明.该成果对非正规目标函数的单机随机排序问题的解决具有一定的参考价值和指导意义.     

带有扩充链优先约束工件的分批排序问题

提出一种工具之间带有扩充链的优先约束的分批排序问题,这种扩充链上既有优先序工件又有无约束工件(工件个数不定)。目标为极小化最大完工时间。优先约束为有m个优先约束集,其中一个"扩充链"上有n个工件,其余m-1条链上的工件数为常数,工件的加工不可中断。问题1chains,B=mCmax为多项式可解,同时给出了问题的一个多项式算法。     

一类工件带有优先约束的分批排序问题

本文对工件带有“扩充链”优先约束的分批排序问题进行了研究,其目标函数为最大完工时间．优先约束为：在一个扩充链上包含有n个工件,另外有m个孤立点工件（即工件之间无任何优先约束）．讨论了时问题的最优算法,把这一问题多项式转化成了组合优化中求解非二部图赋权匹配问题,并相应地给出了一个运算次数为的多项式算法．     

基于准时制的时间成本双目标作业调度优化

提出了一种基于混合遗传算法的以生产周期和生产成本为优化目标的作业调度方法，该方法采用Giffler-Thompson启发式调度算法产生活动的调度，基于工序编码的染色体决定了工序调度的优先级，在启发式调度算法产生的冲突集合中，根据工序的优先级选择下一步安排加工的工序，混合遗传运算在全全局范围内搜索具有最优调度工序优先级的染色体，同时，在GifflerThompson的启发式算法中，采用了反向调度的策略，即从工件的交货期开始，先安排最后一道生产工序，然后依次安排前一道生产工序，直到工件的第一道工序调度完毕，形成一个完整的调度方案，在算法中，不仅考虑了工件的生产周期和多个工艺计划，而且考虑了库存费用和加工费用，设计了基于生产周期和生产成本的双目标适应度函数，算例结果表明该方法是可行的。     

关于问题1|chains,B|Cmax的多项式算法

对带有"扩充链"优先约束的分批排序问题进行了研究,其目标函数为最大完工时间.优先约束为:在一个"扩充链"上包含有n个工件,另外有m个孤立点工件(即工件之间无任何优先约束).讨论了B=2时问题的最优算法,把这一问题多项式转化成了组合最优化中求解非二部图赋权匹配问题,并相应地给出了一个运算次数为O(n4)的多项式算法.     

带有前后约束的延误排序问题的近似算法

把工件之间不带前后约束的延误排序的后移算法移植到带有前后约束的情况, 提出一个多项式时间的近似算法. 这个算法可以快速地得到这种延误问题的近似解.     

考虑作业人员疲劳度均衡的第一类装配线平衡

基于快速全身评估法对所有的作业姿势进行风险评估,考虑不同作业元素优先关系、不相容和同工位等约束,提出融合作业时间和作业姿势相互影响的工位累计疲劳度,构建最少工位数和最小工位累计疲劳度标准差的多目标优化模型,保证装配线工位少且疲劳度均衡.采用基于优先权重的编码,设计多目标粒子群算法,最后通过实例证明本方法的合理性与有效性.     

带有优先约束的分批排序问题

对工件带有优先约束的分批排序问题进行了研究,其目标函数为最大完工时间．优先约束为：有一个树上包含有n个工件,其余的m-1条链上的工件数总和为常数,且工件的加工时间不限制．对于此种情况,给出了一个多项式时间算法．     

关于并列管道型机器排序的复杂性

考虑一个有两个功能部件的机器模型,每个部件要么是有序的,要么类似于管道并列的。关于这类机器模型的3个 NP-完成结果在[1]中有所阐述。本文说明的是当先前限制因素和其他限制因素削弱时,这三个NP-完成结果仍然正确。     

Particle swarm optimization algorithm for partner selection in virtual enterprise

Partner selection is a fundamental problem in the formation and success of a virtual enterprise. The partner selection problem with precedence and due date constraint is the basis of the various extensions and is studied in this paper. A nonlinear integer program model for the partner selection problem is established. The problem is shown to be NP-complete by reduction to the knapsack problem, and therefore no polynomial time algorithm exists. To solve it efficiently, a particle swarm optimization （PSO） algorithm is adopted, and several mechanisms that include initialization expansion mechanism, variance mechanism and local searching mechanism have been developed to improve the performance of the proposed PSO algorithm. A set of experiments have been conducted using real examples and numerical simulation, and have shown that the PSO algorithm is an effective and efficient way to solve the partner selection problems with precedence and due date constraints.     

有限制联盟的加权弱半值

研究了有限制联盟的加权弱半值，指出在有限制联盟条件下，加权弱半值的公理化和E．Calvo等提出的一致。