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

在工件的调整时间和移走时间独立于加工时间的两机器流水作业问题中，同一工件的“调整”步及“移走”步在两台机器上可重叠进行，但“加工”步不能重叠，本以最大延误为目标函数讨论问题的解中工件排列应满足的条件，根据这些条件我们构作了两个近似算法。     

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

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

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

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

调整时间可分离的FlowShop调度问题F3|s|C_(max)

研究了三台机器调整时间可分离的FlowShop调度问题,目标函数为极小化最大完工时间·证明了最优调度可能不是排列调度,但是工件在前两台机器上具有相同加工顺序的调度中至少存在最优调度·在排列调度范围内,对于工件在第二台机器上的调整时间与加工时间之和的最大值不超过工件在第一台或第三台机器上的调整时间与加工时间之和的最小值的情况,给出了求解最优调度分派规则,并以分派规则为基础给出了多项式最优算法     

具有简单线性恶化加工时间的Flowshop调度问题

讨论工件具有简单线性恶化加工时间的FlowShop调度问题·对于两台机器目标函数为极小化最大完工时间的FlowShop调度问题,证明了利用Johnson规则可以求得最优调度·对于多台机器的一般FlowShop调度问题,如果工件在各机器上的加工时间均相等,目标函数为极小化最大完工时间或最大延误的问题可以转化为单机调度问题·如果目标函数为极小化完工时间和,则利用SPT规则可以求得最优调度·     

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

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

两阶段供应链下极小化最大完工时间的单机系列批排序

【目的】考虑单机情况下的加工和运输两阶段的供应链排序问题。【方法】在生产阶段,将所有工件在加工之前划分成批,在一台有限批容量的机器上加工,工件的实际加工时间是关于该工件退化率和加工位置的函数;在运输阶段,有一辆运输车,且每次只能运输一批工件,即车的容量等于批的容量。通过分析用运输车的车容量限制与工件个数的关系。【结果】由最优算法得到了一个最优排序和最小化最大完工时间。【结论】首先给出最大完工时间问题的一个下界,然后指出在当工件个数小于等于运输车的容量限制时,提供出来一个最优算法。对于当工件个数大于运输车的容量限制时,证明了当工件满足一定条件时,该问题也存在最优算法。     

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

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

单机随机加工时间的交货期窗口设置

讨论n个独立工件在一台机器上加工，而且工件加工时间服从正态分布的交货期窗口设置问题，在等宽交货期窗口条件下，确定了工件交货期窗口，并证明这种交货期窗口设置只与窗口设置有关，而与工件排序无关。     

带有可变加工时间和可用性限制的排序问题

研究带有恶化效应、学习效应和可用性限制的单机和2台平行机的排序问题。在这个模型中,工件的实际加工时间与其基本加工时间、加工过程中所排位置及开始加工时间有关;同时由于维修、保养等原因,使得机器在某段时间不能加工工件,即机器具有可用性限制,且维修之后机器性能完全恢复,讨论的目标函数为总完工时间。对于可以在任意时间只维修一次的单机问题,以及只有一台机器具有可用性限制的2台平行机问题,分别给出了拟多项式时间的动态规划算法。特别对于一台机器只在零时刻开始维修另一台机器无可用性限制的特殊情况,通过将其转化为指派问题,给出了复杂性为O(n4)的多项式时间最优算法,并通过一个数值例子说明了其计算过程。     

二机流水作业带不可用区间、工件可拒绝的调度问题

考虑了二机流水作业第一台机器带不可用区间、工件可拒绝的调度问题.所有的工件都是加工可中断的,即当某一工件在不可用区间出现之前开始加工但在机器不可用时并未加工完成,在不可用区间结束后可以接着加工.目标函数是最小化接受加工工件的最大完工时间与拒绝工件的惩罚之和.此问题是NP-难的.首先提出了一个动态规划的最优算法以求解小规模问题,并给出了数值计算实例.所提出的动态规划算法的运算时间随着问题的规模成指数增长,进而又提出了一个启发式算法,并证明了该启发式算法的最坏性能比是3.     

工件具有区间限制的批在线调度

研究同构并行机上的批在线调度问题,目标函数是使最大完成时间(最后一个工件的完成时间makespan)最小.工件以批方式到达且每个批中有m个工件,每个工件的加工时间随其批的到达而给定且限定在某个时间区间上.当一批工件到达时,在对其后批的信息不了解的情况下,要立即对该批中的工件进行调度,调度过程中不允许中断.针对这一问题,给出了一个批在线启发式列表调度算法,在同一批中的工件按LPT规则调度,当一批中的全部工件被调度完后,调度下一批中的工件.对算法的最坏情况进行了分析并给出了算法的竞争率.     

一类多机排序问题算法及其计算复杂性研究

在经典排序论中，一般都假设每个工件在任一时刻仅被一台机器加工，且每台机器至多仅加工一个工件。在这篇文章中，研究这样一类排序问题：每个工件可以被多个不同的机器子集加工，其加工速度对于不同的机器子集是不同的，被加工的工件假定是可以间断且是独立的。排序问题的性能测度是排序长度。在以上条件下求解这类问题算法被给出，对其计算复杂性也作了研究。     

带有准备时间和退化维护的单机排序问题

研究带有可变加工时间、准备时间和退化维护的公共交货期与凸资源分配的单机排序问题.工件的实际加工时间是关于所分配的不可再生资源量和与工件位置有关的退化效应的函数,并且在每个工件加工之前都有一个准备时间,它是有关资源分配的凸函数.为了消除机器的退化,在规划时间内最多允许执行一次维护活动.在资源总量有限的条件下,确定最优工件排序、最优公共交货期、最优维护位置和最优资源分配方案,使得由工件的提前惩罚、延误惩罚、公共交货期和最大完工时间构成的总费用最小.根据优化的相关知识,将问题转化为匹配问题,给出了该问题的启发式算法.     

钢铁企业生产与运输费用协调调度问题

针对钢铁企业生产前存在不可忽略运输的实际,研究了生产与生产前运输费用协调调度问题.由于钢铁企业被调度的工件体积较大及加工前不能等待太长的时间,因此运输车辆的容量及工件在机器前的缓冲等待时间有限制.考虑的机器环境为单机环境,单机前有无限的缓冲空间,运输车辆数目无限,调度的目标函数为传统的调度函数加上运输费用.对于不同的目标函数,证明了工件在单机加工前缓冲等待时间有限制的调度问题是强NP难的,对于运输车辆有容量限制问题的可解情况给出了多项式时间算法.     

圈中t-区间的k-染色问题

考虑客户请求在圈中实现的问题. 每个请求联系着一个t 区间, 由圈上至多t(t1)个区间构成. 要实现一个请求, 需选择它所对应的t 区间中的一个区间并为其安排k种颜色中的一种. 任意两个选定的区间如果在圈上有公共边, 则不能得到同一种颜色. 对目标寻求实现最大数目的请求问题, 给出了一个3.042 近似算法.     

一致性条件下带磨损因子的排序问题

考虑下述带磨损因子的排序问题：n个工件需在同台机器上依次加工，工件j,j=1，2，…，n,所需的加工时间同它被开始加工的时间有关，当工件j开始被加工的时间为t时其所需的加工时间为Pj=bjt，其中bj可视作与工件j有关的一个磨损因子．要求适当排列这n个工件的加工顺序，使某目标函数值达最小．对最大迟后、最大延误、加权完工时间之和这三个目标函数，文中给出了相应条件下的最优算法．     

一类复合并行机排序问题的多项式时间算法

在经典排序论中，一般都作以下两条假设：每台机器在任一时刻至多加工一个零件，每个零件在任一时刻至多被一台机器加工。本文研究在并行加工中多台机器可同时加工一个零件的排序问题，且每个零件可在固定的一个机器的子集上加工。在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究这种问题的计算复杂性。