带转包选项的自由作业排序

本文研究两机自由作业排序问题,工件的两个工序既可以在制造商的两台自由作业环境机器上加工,也可以转包给两承包商加工.每承包商有一台单机,仅能加工指定的工序.工件被转包时制造商需要付出一定数量的转包费用.制造商需要同时确定转包工件集及未转包工件的加工顺序,目标是极小化转包费用与未转包工件时间表加工总长之和.本文根据转包费用系数的不同,分析问题     

求带释放时间的半导体煅烧排序的最短交付时间的一个高效PTAS

本文研究一个目标是最小化最大交付时间的能分批处理的非中断单机排序问题．这个问题来源于半导体制造过程中对芯片煅烧工序的排序．煅烧炉可以看成一个能同时最多加工B（〈n）个工件的处理机．此外，每个工件有一个可以允许其加工的释放时间和一个完成加工后的额外交付时间．该问题就是将工件分批后再依批次的排序加工，使得所有工件都交付后所需的时间最短．我们设计了一个用时O（f（l／ε）n^5/2）的多项式时间近似方案，其中关于1／ε的指数函数厂（1／ε）对固定的ε是个常数.     

具有不同生产时区费用的单机可拒绝排序问题

考虑了单机环境下,机器具有不同的生产时区费用,并且工件的加工是可以拒绝的排序问题.需要选择要加工的工件集合,对每个加工的工件指派相应的生产区间并排序,并支付拒绝加工工件的拒绝费用.对于排序理论中主要的四个目标函数,研究了单位区间的生产费用随着时间的推迟是单调非增的情况,分析了问题的复杂性,对于这些问题给出了它们的最优算法.     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

加工时间离散可控的分批配送排序问题

研究了工件的加工时间是离散可控的,并且工件加工完后需要分批配送到客户的单机排序问题.一个客户在初始时刻将一批工件交给一个制造商进行加工.每个工件有多种加工模式,分配给每个工件的加工资源越多,则其加工时间越短.工件生产完后需要分批配送到客户处,每一批需要花费一定的时间和费用.研究了排序理论中主要的四个目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对具体的问题给出了它们的最优算法.     

具有两个不相容工件族单位工件的有界分批在线排序问题

研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在有界平行分批排序中,容量有限制机器最多可将b个工件形成一批同时加工,每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为■的最好可能的在线算法.     

工件具有加工位置上限最小化加权总误工量的单机排序问题（英文）

考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中,每个工件J_j都具有一个加工位置上限k_j.也就是说,如果工件J_j是一个可行排序中的第x个工件,那么就需要满足x≤k_j.证明了(ⅰ)当工件具有相同工期时,该排序问题是二元NP-难的并且是拟多项式时间可解的,(ⅱ)当工件具有单位权重时,该排序问题是一元NP-难的.     

具有两个不相容工件族单位工件的有界分批在线排序问题

研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在有界平行分批排序中,容量有限制机器最多可将b个工件形成一批同时加工,每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为√17+3/4的最好可能的在线算法.     

极小化总完工时间的同时加工排序

讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.     

工件延误和可拒绝下的单机重新排序问题的近似方案

研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题。在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定。然而,在工件正式开始加工时,工件集中的部分工件由于延误不能按时到达,这对初始排序的执行产生了干扰,所以需要对初始排序进行调整,即重新排序。为了保证服务水平,允许对延误工件拒绝加工,但需支付相应的拒绝费用。调整后的重新排序的目标是在保证接受工件集中工件的最大延误不超过给定的上界的约束下,使得接受工件集的赋权完工时间和,拒绝工件集的拒绝费用和以及接受工件集中工件的最大延误的赋权惩罚费用之和达到极小。对该问题,设计了一个伪多项式时间动态规划精确算法,并利用稀疏技术得到了一个完全多项式时间近似方案。     

单机最优交货期决策及工件排序

本文考虑n个独立工件在一台机器上加工的排序问题,每个工件J_i的交货期设置为d_i=kP_i~α(α≥1),目标是寻找工件最优加工时间乘子及工件最优排序S(?),使工件完工时间与交货期的最大偏差最小。给出寻找最优加工时间乘子k(?)及工件最优排序S(?)的方法。     

订单带多工类工件时的极小迟后范围问题

本文考虑下述由多工类工件组成的订单的单机排序问题：每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类．当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间si．每一订单有一给定的应交工时间,订单的完工时间定义为该定单所含全部工件完工时的时间．我们希望适当排列这n个工件,使得订单的迟后范围最小．相应这一排序问题,文中依不同的背景给出了以下二种模式：同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,用GT,Ba来表示；同类工件一起连续加工,工件的完工时间为其本身的完工时间,用GT,Ja来表示．对于这两种模式的排序同题,我们均证明了其NP-hard性并给出了对应的分枝定界算法．     

具有多个制造商和分批配送的同类机排序问题

考虑了同类机环境下多个工件加工和配送的排序问题.有多个制造商分布在不同位置,每个制造商处有一台机器可以加工工件.不同的机器对应着不同的加工速度和加工费用.工件生产完后需要运输到客户处,每一批配送需要花费一定的时间和费用.研究了排序理论中主要的3个目标函数,分析了问题的复杂性,对于这些问题给出了它们的最优算法.     

单位工件的平行机并行分批在线排序问题的算法

本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J₁,…,J_n}要在m台批处理机上加工。批处理机每次可同时加工至多B(Bj(1≤j≤n)的到达时间为r_j,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。     

带学习效应和资源依赖的单机排序模型

在工业生产中,随着员工操作技能的熟练程度的增加,对于相同的任务越往后加工,所花的时间将会减少。 同时,为了尽早完工,管理者也会考虑给加工工件分配一定量的额外资源来缩短工件加工时间。 本文基于以上实例,讨论了工件的实际加工时间既具有学习效应又依赖所分配资源的单机排序问题。 在问题中,假设工件的学习效应是之前已加工工件正常加工时间和的指数函数。 同时随着分配给工件资源量的增加,工件的实际加工时间呈线性减少,所需费用呈线性增加。对这一排序模型,主要探讨以下五个目标函数:最小化最大完工时间与资源消耗量总费用的和;最小化总完工时间与资源消耗量总费用的和;最小化加权总完工时间与资源消耗量总费用的和;最小化总提前、总延误、总共同交货期与资源消耗量总费用的和以及最小化总提前、总延误、总松弛交货期与资源消耗量总费用的和。 本文对前三个目标函数相应的排序问题给出了多项式时间可求解的算法。 对后两个目标函数所涉及的排序问题借助于指派问题分别给出了时间复杂性为O(n³)的算法。     

工件加工时间随加工顺序变动的单机排序问题

本文讨论了一类工件加工时间随加工顺序而变的单机排序问题,在目标函数sum from i=1 to nC_i与Lmax下,Smith法则与Jackson法则仍然成立。从而推广了Smith与Jackson的结果。一般所考虑的单机排序问题是:有n个工件需要在一台机器上加工,而该机器只能一次加工一个工件,且工件j在该机器上所需的加工时间为P_i,这里P_j为一常量,即与工件早加工或晚加工无关。现在需要确定工件加工的一个顺序,使得在不同的目标下最优。     

基于一般学习效应下的单机排序问题

近来具有学习效应的机器排序问题收到广泛的关注.对于机器排序中工件的实际加工来说,与工件加工位置有关的学习模型更具有现实性.本文研究了工件加工位置和与已经加工过的工件之和有关的一般学习效应模型.首先证明文献中与位置和已经加工过的工件加工时间之和有关的学习模型是本模型的特殊情形.其次对于单机排序问题我们提出一般解法.     

具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案

本文考虑了机器具有不可用区间且工件可拒绝下的单机重新排序问题,在该问题中,给定一个工件集需在一台机器上加工,每个工件有自己的加工时间和权重,且对该工件集目标函数为极小化总加权完工时间的排序计划已给定,根据该排序计划中每个工件的完工时间已确定每个工件的承诺交付时间。然而,在工件正式开始加工前,原计划用于加工的某段时间区间因临时用于检修机器而导致机器在该时间区间不再可用,需要对工件重新排序。为了确保在新的重新排序中,工件的延误成本不致太大,决策者可以选择拒绝部分工件,但需支付相应的拒绝费用。任务是确定接受工件集和拒绝工件集,并将接受的工件在考虑机器具有不可用区间的条件下重新排序使得接受工件集的总加权完工时间,总拒绝费用及赋权最大延误之和最小。该问题是NP-困难的,对此给出了伪多项式时间动态规划精确算法,利用稀疏技术设计了完全多项式时间近似方案。     

一个非常规目标函数的单机随机调度的最优策略

本文考虑了n个工件在同一台机器上加工的调度问题 ,其中工件的加工时间和交货期都是具有任意分布的随机变量 .我们考虑了一个非常规目标函数 ,其中工件的权数与平均加工时间成比例 .在工件的交货期与加工时间满足相容条件下 ,得到了个简单的最优排序策略 .     

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,同题可能会无可行排序.先讨论了问题的可行性.如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间.而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序.