单机总误时排序问题的序扩张

单机总误时排序问题的序扩张林诒勋（郑州大学数字系，郑州４５００５２）ＯＲＤＥＲＥＸＴＥＮＳＩＯＮＳＦＯＲＴＨＥＳＩＮＧＬＥＭＡＣＨＩＮＥＴＯＴＡＬＴＡＲＤＩＮＥＳＳＰＲＯＢＬＥＭ￥ＬＩＮＹＩＸＵＮ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，Ｚｈ...     

以延误时间为指标的一台设备上的排序问题

在工业生产中常常会碰到这样的问题:有若干种产品要在某台设备上加工,每种产品都有预定的交货日期,并且这台设备不能同时加工两种产品.由于活多时间紧,某些产品免不了要延误交货日期.如何安排这些产品的加工顺序,使各产品延误交货日期的总时间最少?这是属于以延误时间为指标的一台设备上的加工顺序问题.对于这类问题,目前尚未完全解决.本文提出一种近似解法,似比国外流行的一些解法要好些.现叙述如下:     

两台单机的合作排序问题

本文研究下面情形的排序问题,两个代理商联合加工来自客户的一个工件集,每个代理商仅有一台单机用于加工工件,每个工件仅需被其中的一台单机无中断地加工一次.在完成分配工件的加工任务后,每个代理商将获得一定的收益并付出一定的加工费用.需要找出工件集的一个最优划分,使得两个代理商的净收益乘积最大.本文研究三个不同经典排序目标作为加工费用的两机合作排序模型,证明模型复杂性,分析最优解结构并设计动态规划算法.     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

一个单台机器排序问题的下界

本文考虑下述n个工件在一台机器上加工的排序问题。其中d_i,C_i,w_i和h_i分别为工件i的应交工时间、完工时间、延误权因子和成本权因子。工件i所需的加工时间为p_i,所有工件在时间t=0时同时到达机器旁,机器不允许空转,工件被加工时不允许中断。本文用一O(n)快速方法给出(P)的一个下界。对问题(P),当取O≤u_i≤w_i,i=1,2,…,n时,     

有提前和延误损失的一个排序问题

在工农业生产中,有些任务提前去做会产生一定的损失,拖后去做也会有一定的损失.根据这一实际问题,可抽象出如下的数学模型:问题设有n个被服务单位J_1,J_2,…,J_n,需要一个服务单位为他们服务,它们被服务的时间分别为t_1,t_2,…,t_n;允许开工的日期为c_l,c_2,…,c_n;应交工的日期为d_1,d_2,…,d_n,且设c_i+t_i≤d_i,i=1,2,…,n;如果被服务单位J_4未到允许开工的日期就得到服务,那么提前每单位时间造成的损失为a_i(i=1,2,…,n);如果被服务单位J_4不能按时交工,那么延误每单位时间造成的损失为b_i,i=1,2,…,n.试问,如何安排一个服务次序,使之     

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

研究了最小化总加权提前损失单机排序问题,其中提前损失是工件在工期之前完成的各部分的持续加工时间.首先,文章分析了总加权提前损失问题在中断情况下的复杂性,提出了中断排序算法,用算例进行了验证;接着通过设计拟多项式动态规划算法,说明该问题在非中断情况下是一般意义下NP难的,并进行了数据实验,验证了该算法的有效性.     

具有禁用区间的单机最小化加权完工时间和排序问题

研究具有禁用区间的单机最小化加权完工时间和排序问题.在该问题中,有一些禁用区间已经固定在机器上,工件将被安排在其余自由区间内进行加工且不能与禁用区间重叠.在文献中已经证明,该问题是强NP-困难的,并且在P不等于NP的假设下,该问题不存在2~(q(n))-近似算法.其中,n是工件个数,而q(n)是n的任一多项式.但是,其精确最优算法尚属未知.给出了该问题的一个动态规划最优算法.当禁用区间的数目是固定常数时,该算法是拟多项式的.     

目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法

本文研究了两台机器带柔性维修时间限制的排序问题,其中第一台机器在固定的时间内必须进行维修,而第二台机器一直可用,目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题,我们给出了一个性能比为的近似算法,并证明了该性能比是紧的。     

最小化最大加权完工时间重新排序研究

重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是:1)在原始排序错位限制的条件下最小化最大加权完工时间;2)最小化最大加权完工时间与原始排序的错位的加权和.在本文研究中我们假设所有工件在0时刻到达.文章的主要结果:对于Γ∈{D_(max)(π~*),△_(max)(π~*)},给出了问题1|Γ≤k|max w_jC_j和问题1‖maxw_jC_j+μΓ多项式时间的求解算法;证明了问题1|∑△_j(π~*)≤k|max w_jC_j和问题1‖max w_jC_j+μ∑△_j(π~*)是强NP-困难的.     

最小化总完工时间与分批费用之和的有界分批排序问题

考虑了当每分一批均产生固定费用、批容量有界且为固定值b、加工不允许中断抢先.所有工件在零时刻到达时的单机平行分批排序问题.目标是最小化总完工时间与分批费用之和.利用动态规划方法给出了多项式时间算法,时间界为O(n~(b(b-1))).     

最小化提前/延误赋权工件数及时窗惩罚的排序问题

研究赋权提前/延误工件数的公共时窗单机排序问题,时窗的位置和大小待定且由惩罚费用衡量.首先给出最优排序的一些性质,进而提出一个多项式时间算法以最小化这些费用的和.     

工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.     

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

研究了与总误工损失相关的两个代理的单机排序问题。第一个代理以工件的总误工损失为目标函数,第二个代理以工件的总完工时间或总误工工件数为目标函数。目标是寻找一个排序,使得在第二个代理的目标函数不超过给定的上界的条件下,第一个代理的目标函数值最小。对这两个与总误工损失相关的两个代理的单机排序问题,分别给出它们的拟多项式时间的动态规划算法。     

单可变资源最小化加权完工时间和排序问题的强NP-困难性

Baker和Nuttle提出了下述单可变资源排序问题：扎个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的．当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的．最近,Yuan、Cheng和Ng证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的．本文我们证明了该问题是强NP-困难的．     

单可变资源最小化加权完工时间和排序问题的强NP-困难性

Baker和Nuttle提出了下述单可变资源排序问题：$n$个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,Yuan、Cheng 和 Ng 证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的.     

两台单机的合作排序问题北大核心CSCD

本文研究下面情形的排序问题,两个代理商联合加工来自客户的一个工件集,每个代理商仅有一台单机用于加工工件,每个工件仅需被其中的一台单机无中断地加工一次.在完成分配工件的加工任务后,每个代理商将获得一定的收益并付出一定的加工费用.需要找出工件集的一个最优划分,使得两个代理商的净收益乘积最大.本文研究三个不同经典排序目标作为加工费用的两机合作排序模型,证明模型复杂性,分析最优解结构并设计动态规划算法.