一类排序问题最优工序定义的等价性

在工厂另件加工车间,设有n个另件J_i(i=1,2,……,n)要在m台机床M_k(K=1,2,…,m)上加工,各个另件根据工艺上的要求按一定的顺序通过这些机床,如何安排这些另件的顺序,使予先给定的指标达到最优,这就是运筹学中的所谓排序问题。设J_1,J_2,……,J_n为某一给定的加工顺序,本文涉及的排序问题假定: (1)每一J_i(i=1,2,…,n)都依次通过M_1,M_2…,M_m;每一M_k(K=1,2,…,m)都依次加工J_1,J_2,…,J_n;     

同顺序3×n排序问题的一种方法

本文研究[1]、[2]中的一类排序问题。[3]中证明了当m≥3时同顺序m×n排序问题属于“NP完备”问题。我国数学家越民义、韩继业在[2]中给出了综合使用分支定界法和消去法的很好的结果,但因需计算下界,难免要进行大量的计算。本文在[6],[7]的基础上对一般的3×n问题提出了一种较优序的排序方法,给出最优序的一个选择定理和最优序的一种选择方法。在对几个典型例题进行实算时,应用该法极其简捷地求得了相应的最优序。     

关于同顺序m×n排序问题中总工时下界的一种简便算法

本文对越民义、韩继业《同顺序m×n排序问题的一个新方法》(见《科学通报》1979,18,pp.821~824)一文关于下界B(S…S″)的算法中需大量反复计算的t_m-1m(R_m.)给出了一种简便算法,同时,又对其所提出的下界B(S…S′)的算法作了改进.从而提高了B(s…s′)的估值精度.     

一个排序問題

本文讨论n个另件在m台机床上加工的排序问题。以T.C.Hu引入的(H)矩阵为工具,讨论了Nabeshima充分条件与Johnson—越—韩充分条件之间的关系。在引入PX条作之后,得到了另一个充分条件(定理6)。它在验算的手续上比Johnson—越—韩的要简单些,但在要求的前提上,比后者略微强一些。     

一类计划排序问题确定相邻两零件次序的条件

文中考虑n个零件在m台机器上加工且在每两台机器加工时段之间存在停歇时段,以总加工时间最小为目标当零件加工同顺序的排序问题。其主要结果是将同顺序m×n排序问题中著名的越——韩条件推广到有停歇时间的问题中,得到两个确定相邻两零件次序的条件(定理4,定理5)。     

排序问题中求工时矩阵最大可行和的一种算法

本文通过引进一种关于斜阵的某些概念提出了同顺序m×n排序问题中总工时的一种计算方法。同时,文中指出的空闲时间矩阵说明了对于最优序和较优序,仍存在可以利用这m台机器再进一步加工这n个工件以外的工件的机会。并且,从该方法出发可以进一步提出一种解决关于m×n排序问题的方法。     

关于"Fm|prmu|Cmax问题"的算法

Fm|prmu|Cmax,即m(m>2)台机器同顺序加工n个工件问题是一类重要的车间作业排序问题.对于给定加工顺序的n个工件的排列排序,排序时间表长即任务的最后完工时间的计算可以通过与问题对应的有向图的关键路的计算得到.本文从关键路的结构特点和性质出发,提出了在关键路的基础上将前后相邻的两个工件的加工时间进行比较,然后择优排序的方法,使Johnson SM算法可以在多台机器上得到一定程度的推广,从而使该问题的解法得到明显简化.     

关于F2‖Cmax问题最优解的充要条件

F2‖Cmax问题即二台处理机同顺序加工n个作业问题,是一种常见和重要的车间作业排序问题.求解这个问题用SPT-LPT算法[1]一般不会得到全部最优解,以ai,bi分别表示作业i(1≤i≤n)在二台处理机上的加工时间,其算法中的条件即所有前后相邻接的两个作业都必须满足不等式m in(ai,bj)≤     

排序问题计算加工时间的一种方法及其一个应用

本文提出一种所谓“斜列和”法来计算m台机床加工n个零件的排序问题的加工时间,并对m=3给出两个相邻零件加工先后次序的一个判别条件,以及最前或最后两个相邻零件排序的一个判别条件。     

同顺序m×n排序问题中最优序的一个判别定理

本文所研究的问题只限于[1]、[2]中的同顺序m×n排序问题。当m≥3时,m×n排序问题属于“NP完备”问题。目前,该问题的解决方法为分支定界法和消去法,但用这两种方法求最优序一般都要进行大量的计算。这里,在改进了[6]中算法的基础上,给出了关于在任何一台机器上加工结束时出现的总的空闲时间的分解定理,并进一步提出了一个关于最优序的判别定理,为提出一种解决m×n排序问题的方法提供了理论依据。     

有限制条件的单台机器的排序问题

根据给定n个工件在一台机器上加工时工件间的先后关系 ,定义了一个n个顶点的有向图D ,简化图D得排序图D ,通过穷举图D 的顶点的拓扑序列 ,搜索出了n个工件完工时间之和最小、机器加工完n个工件总时间最少和延误损失最少的加工顺序 .     

n个零件在m台机器上加工有停歇时间的计划排序问题

本文就n个零件在m台机器上加工且在每两台机器加工时段之间存在停歇时段,以总加工时间最小为目标的排序问题当零件加工同顺序时进行讨论,给出了m=3时的分支——定界算法,是文[1]方法的推广。     

带有退化和资源约束的不同类型机排序问题

讨论带有线性退化和线性资源约束的不同类型机排序问题。每个工件都有一个基本加工时间。工件的实际加工时间是与他的基本加工时间、开始加工时间、实际加工位置以及被分配的资源量相关的一般函数。分别讨论了2个排序问题,一个目标函数为每台机器的最大完工时间、总完工时间、加工时间绝对差以及资源分配之和;另一个目标函数为每台机器的最大完工时间、总等待时间、等待时间绝对差以及资源分配之和。目的是同时确定最优资源分配和工件最优的加工顺序,从而使每个目标函数极小化。通过将每个问题的目标函数转化为对应的指派问题,进而求解,并证明每个问题都是在多项式时间内可解的。     

带有恶化效应和维修恶化的单机工期指派问题

研究了同时带有恶化工件和机器恶化维修的单机工期指派问题。工件的实际加工时间是与工件基本加工时间和工件在排序中的实际加工位置相关的一般函数。机器维修时间与其开始维修时间有关,是其线性恶化函数。研究的目标函数是加权提前、延误和工期之和,目的是确定工件的最优加工顺序、公共工期及维修位置,使目标函数最小。将此问题转化为指派问题,从而证明了该问题在多项式时间内是可解的。对于问题的一种特殊情况进一步给出了一个复杂性为O(n2log n)的最优算法。     

带有线性退化工件和退化维护时间的单机窗口排序

排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注。排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用。在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的。文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间;2)工期窗口的位置和大小;3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小。文章最后给出了这个问题的最优算法,其时间复杂性是O(n2logn)。     

带有恶化和拒绝的工期指派的单机排序问题

讨论带有恶化和拒绝工件的工期指派的单机排序问题。工件的实际加工时间是其开始加工时间的线性增函数。如果工件被拒绝,则有一个惩罚费用,否则工件被加工。每个工件都要确定一个工期,文章讨论的工期指派分为CON(共同工期指派)和SLK(相同松弛工期指派)两种情况。对于CON工期指派问题,其目的是确定最优公共工期及工件的加工顺序,使工期、提前、延误和拒绝的总费用最小。将该问题归结为一系列指派问题,从而得到了一个复杂性为O(n4)的算法来求解此问题。对于SLK工期指派问题,目的是确定最优的松弛量及工件的加工顺序,使松弛、提前、延误和拒绝的总费用最小。将其归结为一系列指派问题,给出了求解此问题的多项式时间的最优算法。     

以总加权完工时间为目标的两台机越库排序的动态规划算法

提出并研究两台机器环境下的以带权总完工时间为目标函数的越库配送排序问题.越库作业的入库与出库车辆被看作是排序问题中的机器,入库货物与客户需求为具有前序集限制关系的被加工工件.研究了该问题的计算复杂性及其最优解的若干性质,提出求解该问题的逆向动态规划算法,并给出了动态规划算法的数值实验.结果表明,所提出算法至少可以求解25个工件规模的越库配送排序问题.     

流水车间排列排序专家系统—PFSCH

流水车间排列排序问题可以简单表示为:n/m/p/F_(max),其含义为,n个不同的工件(J_1,J_2,…,J_n)要经m台机器(M_1,M_2…,M_m)加工;加工路线为M_1—M_2—…—M_m,n个工件在每台机器上的加工顺序都一样;p表示排列排序;目标函数是使最长流程时间F_(max)(加工周期)最短.n个工件有n!种不同的加工顺序.现已证明,n/m/p/F_(max)(m≥3)问题属于NP难题,找不到多项式时间算法.因此,人们提出了若干个启发式算法,其中最著名的是Campbell等人提出的启发式算法(简称为CDS法).Dannenbring曾比较过11种不同的启发式算法的效果,指出“快速接近扩展搜索法(RAES法)”的结果最好.但是,RAES法实质上还是一种列举法,它不从问题本身的结构出发,具有很大的盲目性.虽     

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

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

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

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