有分离调整和移走时间的两机器no-wait流水作业最大延误问题

以最大延误为目标函数，讨论了两机器no—wait流水作业问题解中的工件排列应满足的条件，并根据这些条件给出了几个近似算法．     

有分离调整和移走时间的两机器流水作业总延误问题的近似算法

讨论了一类两机器流水作业的总延误问题,其中每个工件的操作由“调整”步、“加工”步及“移走”步组成,而工件的调整时间和移走时间均独立于加工时间,同一工件的“调整”步及“移走”步在2台机器上可重叠进行,但“加工”步不能重叠,并且第一台机器上没有空闲时间,工件一旦开始加工就不允许中断．给出了该问题的解中工件排列应满足的条件,并根据这些条件构建了几个近似算法．在构建分支定界算法时,利用问题目标函数的下界及近似算法的结果给出了剪支法则,由此说明所给近似算法对某些例子是很有效的．     

有调整时间的两机器流水作业总流程问题

在两机器流水作业问题中 ,每个工件在加工前有一调整时间 ,同一工件的调整是可以重叠的 ,但加工时间不能重叠 .本文以总流程为最优准则研究调整时间独立于加工时间的两机器流水作业问题 ,给出了问题最优解中工件排序应满足的条件 ;其次讨论当工件的两种时间满足一定条件时最优时间表的求法 ;最后给出几个近似算法     

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

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

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

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

由两台柔性机器组成的流水作业问题

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

具有学习效应的两台机器流水作业排序问题

讨论了具有学习效应的2台机器流水作业排序问题,目标函数为极小化总完工时间.首先证明了2个相关引理,基于2个引理和对问题的分析,证明了用SPT算法解决问题的界为一个与工件的最小加工时间和最大加工时间相关的且小于2的一个值.     

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

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

加工时间线性恶化的成组加工流水作业问题

文章讨论了m台机器的Flow Shop成组加工问题.工件在不同机器上的加工时间以相同的系数(斜率)线性恶化.目标函数分别为极小化时间表长和总完工时间.对于目标函数为极小化时间表长的Flow Shop成组加工问题.再进一步细分为组间无调整时间和组间有相同调整时间的两种情形来讨论,都得到了最优调度(排序).对于目标函数为总完工时间的Flow Shop成组加工问题,只要组内按qij单调递增(SPT)序加工,组间按S.单调递增序加工可得最优调度.     

一种受限于给定最大延误上界的单目标启发式算法

基于有效求解在未超过给定的最大延误上界这一约束条件下最小化总完工时间的置换流水车间调度问题,提出一种新的迭代贪心启发式算法IG_CZ,通过结合全局和局部优化策略获得最优解或近似最优解.并在Taillard基准测试集上对不同规模的问题进行算法性能测试,实验结果表明,IG_CZ算法不仅简单、易于实现,而且求解能力及解的质量优于对比的其他算法。     

序列相关Setup单机调度的最小化最大拖期分枝定界算法

研究了具有序列相关Setup带交货期的单机调度NP问题,优化目标是最小化最大拖期.通过松弛子路径连通约束,提出了基于AP算法的下界方法.在算法下界的基础上,基于下界解建立了以改进Karp-Steel补偿启发式方法构成的上界构造方法.发现了反映问题特性的两条优势规则.最后依托Ragatz提出的分枝定界算法框架,引入上界和下界方法,以及两条优势规则,形成了求解该问题的分枝定界枚举算法.通过计算实验证明了算法的有效性.     

加工时间可变最大流程时间排序的纳什合作博弈

在现实世界中,往往存在一人无法承担一个项目中全部工件加工任务的情况,这就要考虑由多人合作加工的情形.本文研究工件加工时间是开工时间线性函数的情况下,以最小的最大流程时间作为加工成本的(两人)纳什合作(加工)博弈问题,每人有一台用于加工工件的机器.通过确定这批工件的一个恰当划分,把工件分配给两台机器,使得相应的合作(加工...     

用GA算法解不确定条件下Job Shop的提前/拖期调度问题

研究了具有公共交货期窗口的 Job Shop的提前 /拖期调度问题 ,并考虑了处理时间的不确定性 ,采用三角模糊数表示不确定性信息 ,提出了基于遗传算法的优化方法并以仿真实验验证了算法的有效性     

并行加工系统“提前／拖期”排序问题研究

通过对现有单机Ｅ／Ｔ排序问题的研究，建立了一类相 应的多机并行加工系统的Ｅ／Ｔ排序模型，模型的优化目标为工件排序的提前与拖期损失的总罚值为极小。还给出了一个工程实用型启发 式排序算法。     

固定区间下的可中断单机双代理总加权误工问题

【目的】研究在固定区间内工件可中断的单机双代理排序问题。【方法】每个代理都有各自对应的工件集合以及目标函数，它们只能共同使用1台机器来完成各自工件的加工，每个代理的目标都是最小化各自的目标函数。第一个代理工件可中断且到达时间与工期满足一致性关系，目标函数为总加权误工费用；第二个代理中工件位于固定时间窗口内进行加工。【结果】排序的目的是为了第二个代理中工件满足加工时间区间等于固定区间条件下，使得第一个代理的目标函数达到最小化。【结论】利用了分块的原则，给出了最优性质刻画和复杂性分析，以及设计了一个伪多项式时间动态规划算法。     

A Genetic Algorithm for Single Machine Scheduling with Fuzzy Processing Time and Multiple Objectives

IntroductionMachineschedulinghasbeenoneoftheconsiderableresearchtopicsoverthelastdecades.BranchandBoundalgorithmsfordeterminingtheoptimalmakespanhavebeendevelopedandtestedonsmallsizedproblems.Inaddition,dispatchingrulebasedheuristicalgorithmshavebeenproposedinordertominimizespecificperformancecriteriasuchasflowtime,earliness/tardiness,makespanetc.Theschedulingproblemisknownasthen/m/p/cmaxproblem[1].Inthespecialcaseofm=1,theproblemisdescribedastheonemachineschedulingproblem.Manyresearchersdea…