关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。     

关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。
     

关于总加权提前损失的两个代理单机排序问题

[目的]研究与总加权提前损失有关的两个代理单机排序的问题.[方法]第1个代理工件的工期相同,目标函数是最小化总加权提前损失;第2个代理的目标函数是最大正则函数,它的特殊情形为最大完工时间.目标是寻找一个排序,使得在满足第2个代理目标可行的情况下,第1个代理目标函数值最小.[结果]利用背包问题证明了该问题是一般意义下NP难的.[结论]最终给出了总加权提前损失有关的两个代理单机排序问题的一个最优算法,并证明了该算法是拟多项式时间可解的.     

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

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

带有固定区间的双代理排序问题

【目的】研究带有固定区间的双代理排序问题。【方法】第一个代理的工件加工过程可以中断，考虑两种机器类型：单台机器时考虑的目标函数为总权误工损失或总权提前损失；两台平行机时考虑的目标函数为总完工时间，同时必须在规定的固定区间加工第二个代理的工件，目标是在满足第二个代理目标的可行性前提下寻找一个使第一个代理的目标函数值更小的排序方案。【结果】设计了单台机器固定区间工件损失问题的排序算法，也为两台平行机总完工时间问题设计了相应算法。【结论】设计的算法可在多项式时间内得到解决，且证明了算法的最优性，并用数值实验说明了算法的可行性。     

两个代理的单机排序问题的多项式时间算法

考虑两个代理的单机排序问题,有两个代理A和B,分别具有各自的工件集JA和JB,并且代理A中所有工件的加工时间都相等.第一个代理A以加权完工时间和为目标函数,第二个代理B以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得第二个代理B的目标函数不超过给定上界Q(Q>0)的情况下,第一个代理A的目标函数达到最小.文章证明该问题可以在O(nlogn)内求解.     

共同工期下的总权误工单机双代理排序问题

【目的】研究共同工期下与总权误工相关的单机双代理排序问题。【方法】通过动态规划方法分析了双代理模型，即在第2个代理的总误工工件个数不超过一个给定值的前提下，使得第1个代理的总权误工最小。【结果】分别给出了最优性质、伪多项式时间算法以及时间复杂度分析。【结论】通过算例实验分析说明了算法的可行性。     

Two single machine scheduling problems with a learning effect

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

具有恶化效应的双代理单机最优调度算法

针对单机床加工环境中待加工任务具有恶化效应且来自2个具有不同需求的代理时,无法快速求解出满足要求且成本最低的最优加工序列的情况,提出了可在特定约束条件下的具有恶化效应的双代理单机最优调度算法。首先提出优化目标为:保证一个代理的任务均不延迟完工的前提下,使得另一个代理的总加权完成时间或总加权折扣完成时间最小;其次指出该优化问题具有NP难度,并给出其在一般及特殊情况下最优解的结构性质;此后对于特定约束条件下的情形,提出多项式时间优化算法。该算法中首先将2个代理的任务分别按照所证明的最优策略排序,然后再按照使得2个代理能得到最小总加权完成时间和给定约束关系的算法将2个序列合并在一起,并证明得出的序列即为所求调度问题的最优解。实验结果表明,该算法作为确定性算法,计算时间与最优解平均误差率大于0.3%的模拟退火算法相似,远远低于可求解出最优解的分支定界算法。     

最大延迟限制下两个代理的重新排序

两个代理的重新排序问题是指,每一个代理有一个非中断加工的工件集,两个代理共用一个机器进行加工,每一个代理分别考察依赖于各自工件完工时间的目标函数.针对单机上有限错位和原始工件集最大延迟限制下,使得新工件集的最大延迟或总加工时间和最小的多代理重新排序问题,设计出几个这类问题的多项式或拟多项式时间的算法.     

时间相关的单机排序的最坏竞争比分析

本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题.工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工.本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比.进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法.     

单机总误工问题的分解启发式算法

为了解决单机总误工问题,提出了一种分解启发式算法。该算法是将解决这一问题最好的优化方法(Lawler分解算法)和非常有效的启发式算法(MDD)有机结合,在每一次迭代过程中均利用MDD算法估计Lawler分解算法中不同分解位置对应的误工,确定具有最大加工时间的工件在获得最小总误工的分解位置处加工。从理论上证明了该算法得到的排序结果优于MDD排序,仿真实验也表明该算法得到的结果99%以上为最优排序,而且可以求解多达1000个工件的问题。该算法以较短的时间获得了接近最优排序的结果,算法性能优良。     

误工工件个数和最大费用函数的单机双代理KS公平定价问题

【目的】考虑把资源分配的公平价格问题应用到单机双代理排序中,这里的双代理就是两个代理具有各自的工件集,公平竞争的安排在单台机器上加工自己的工件。【方法】第一个代理的目标函数为在共同工期的前提下最小化总权误工工件个数,第二个代理的目标是为最小化最大费用函数。【结果】给出公平效用的概念和KS公平定价的概念,进而给出了一般情况下KS的价格公平结构性之和紧界分析。【结论】推广了已有文献的结果。     

时间相关的单机排序的最坏竞争比分析 (运筹学与控制论)

本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题。工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工。本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比。进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法。     

带有安装时间以及可分批加工的供应链排序问题

研究了单制造商多客户的供应链排序问题;同一客户的工件可以分批进行加工,不同客户的工件不可以在一批中加工;当相邻的两批工件属于不同客户时则需要相应的安装时间.以生产和运输总费用最小为目标函数,建立了集成排序模型;分别用工件的加权总完工时间和最大延迟作为排序目标,采用动态规划的技巧给出了最优算法,并分析算法复杂性.     

具有共同松弛时间的恶化型工件排序问题研究

研究工件加工时间具有恶化效应的单机松弛工期排序问题.其中恶化效应指的是工件的实际加工时间是其开工时间的递增函数且所有工件的恶化率相同,工件的松弛工期等于其实际加工时间加上共同的松弛时间.目标是确定工件的一个排序和工件工期的共同松弛时间使得工件的提前时间、延迟时间和工期的共同松弛时间的线性加权和达到最小.用运筹学方法证明了该问题可以转化为两个向量的乘积问题,从而多项式时间可解,并给出了求解的最优算法.     

平行机上单位加工时间加权总完工时间排序问题的反问题

在给定工序下,排序问题的反问题研究目标是对于预先给定的加工任务,要求确定加工时间或者工件权重的最小调整值,使得给定的工件排序最优。本文研究了平行机上单位加工时间的加权总完工时间排序问题的反问题,即对于给定的加工工序,在不同范数下,通过最小限度调整工件的权值,实现给定加工工序最优,同时满足调整权值后,目标函数值不超过原来的值。     

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

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

退化条件下的工期指派的单机排序问题

研究退化条件下的工期指派的单机排序问题。每个工件均有一个关于工期的连续非减的惩罚函数。工件的加工时间是退化的,即工件的加工时间是其开始加工时间的一个线性增函数,所有工件都有一个相同的退化率。目标是确定工件的最优加工顺序、最优工期和最优开始加工时间,使总工期、误工工件数及总完工时间之和最小。工件在工期之后完成则称为误工工件,工件在工期之前完成则是提前工件。工期指派分两种情况,一种是所有的工件工期都相等,另一种是不同的工件有不同的工期。对于上述两种情况分别给出了最优解的3个性质,并且证明了这个问题是多项式时间可解的。     

工期窗口指派可控处理时间资源约束最大费用最小化排序问题

【目的】研究具有公共工期窗口指派的凸资源单机排序问题。【方法】任务的处理时间与所在位置有关,并且可以通过分配一定的资源加以控制,是所获得的资源量的凸函数。目标函数是所有任务费用中的最大值。考虑两个问题。第1个问题是在资源总量有上界限制条件下,确定任务的最优排序、公共工期窗口位置和大小以及资源分配方案,使得最大费用最小。第2个问题是在最大费用有上界限制条件下,求出最小资源总量、任务排序和公共工期窗口位置和大小,使得资源总量最小。【结果】将上述问题转化为非线性凸规划问题和指派问题加以处理。证明了两个问题均可以在多项式时间内求解。【结论】对于考虑的两个问题分别给出了多项式时间最优算法。