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

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

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

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

订单带多类工件时的极小完工时间之和问题

该文考虑下述订单问题：m份订单中共有n个工件需要在同一台机器上加工，这n个工件分属五种不同的类，当机器从加工某一类中的工件转向加工不同于它的第j类工件时，需要一个安装时间Sj，机器加工第一个工件前也有相应于该工件所属类的安装时间，目标是寻找一个使得m份订单的完工时间之和最小的加工顺序，文中根据安装时间、订单完工的定义的不同，分了三种情形，并分别给出了多项式时间算法、分枝定界算法和启发式算法。     

工件可拒绝平行机排序

考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.如果拒绝一个工件,要花费一定的惩罚费用;如果接受这个工件,在m台机器中的一台上分批加工,定义一批的加工时间为这批中所包含的最长工件的加工时间.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的数时,给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案.     

一类两机器 no-wait 流水作业总完工时间问题

在两机器 no-wait 流水作业问题中,每个工件在加工前有一调整时间,加工完之后有一移走时间,同一工件的调整和移走是可以重叠的,但加工时间不能重叠,同时任一工件在第二台机器上的加工必须紧接在它在第一台机器上的加工之后进行,本文以总完工时间为目标函数,讨论问题最优解中工件排列应满足的条件;其次讨论当工件的三种时间满足一定条件时最优时间表的求法;最后为问题设计了一个近似算法.     

机器不同时开工平行机排序问题的原始阈值算法

对于机器不同时开工排序问题,研究m台机器的情况,给出原始阈值算法PTm(ε)(其中ε为可选参数),并证明当ε=m-1m时原始阈值算法PTm的近似比为1 m-1m,而且证明该界是紧的。由此推广原有文献中两台机器的原始阈值算法。     

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

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

并行加工的完工时间

 p台机器完成加工n项任务所需要的时间称为这n项任务的完工时间.首先引入一种参数,即膨胀系数,并设计出一种加工n项任务的算法,然后分别讨论n项任务全都平均分成p份或者全都不分时被p台机器按所设计算法加工的完工时间.     

工件可中断的周期维护混合平行机调度问题

有m台平行机,其中m_1台机器需要周期维护,记m_1台机器每次维护时长为w,维护周期为T,余下的m-m_1台机器不需要周期维护,有n(n m)个加工时长相同的工件被放在m台机器上加工,工件在加工过程中可中断,通过分类讨论的方法,目标函数是最小化时间表长,同时给出相应的最优多项式时间算法。     

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

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

具有延迟时间的自由作业排序问题——最坏性能比分析

研究一类具有延迟时间的自由作业问题，证明在机器台数任意的情况下，一个简单的贪婪算法的最坏性能比不超过2。特别当m＝2时，证明了该算法的最坏性能比为3／2，其中m为机器的台数。     

Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times

Scheduling unrelated parallel machines with controllable processing times subject to release times is investigated. Based on the convex quadratic programming relaxation and the randomized rounding strategy, a 2-approximation algorithm is obtained for a special case with the all-or-none property and then a 3-approximation algorithm is presented for general problem.     

Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times

Theproblemconsideredinthispapercanbestatedasfollows:AsetofnjobsJ={1,2,…,n}aregiventobeprocessedwithoutinterruptiononasetofmunrelatedparallelmachinesM={1,2,…,m},suchthateachjobonlyneedstobeprocessedbyoneofthemachines.Eachjobj∈Jisassignedagivenweightwj,denotingitsrelativeimportance;anormalprocessingtimepi,jandareleasetimeri,jdenotetheearliestpointintimewhenjobjcanbeprocessedonmachinei∈M.Theprocessingtimesofjobsarecontrollableinthefollowingmanner[1,2,6]:Thenormalprocessingtimepi,jofjobjcanb…     

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

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

带运输时间和一个不可用约束的两台平行机排序

考虑了两台平行机的排序问题,其中一台机器带有一个固定的不可用约束区间,任务的加工是不可中断的,而且每一个任务带有一个运输时间,目标函数是最小化最大运输完工时间.这个问题是强NP-难的.提出一个最坏情况比是8/5的多项式时间近似算法,并指出这个界是紧界.同时还用动态规划方法求解该问题.     

基于核主成分分析与最小二乘支持向量机结合处理时间序列预测问题

探讨了最小二乘支持向量机时间序列预测的方法,提出了用核主成分分析提取主元,然后用最小二乘支持向量机进行预测.通过实验表明,这种方法得到的效果优于没有特征提取的预测.同时与主成分分析提取特征相比,用核主成分分析效果更好.     

基于GATS混合算法的最优作业切换不相关并行机成组调度研究

不相关并行机调度问题是车间调度中的典型问题,而单件小批量生产模式导致频繁的作业切换和大量的作业切换时间,降低了设备利用率和生产效率。文中提出了基于成组技术的排序依赖作业切换时间的不相关并行机调度问题研究。根据工件加工所需资源的相似性进行工件聚类成组,满足机器约束条件确定所有工件组在各机器上的分配,以及确定同一台机器上的各工件组以及组内的排列顺序。以最小化总拖延时间为优化目标构建了数学模型,应用了遗传禁忌搜索(GATS)算法进行求解,针对不同规模的问题分别对比人工蜂群(ABC)算法和遗传模拟退火(GASA)算法进行案例研究。对比结果显示文中提出的算法具有较好的寻优能力。     

强制工期相等的双机流水车间排序问题

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

偏差最小化的单机排序问题

提出寻找ｎ个独立工件在一台机器上加工,使工件完工时间与平均完工时间的平均绝对偏差（ＭＡＤ）最小的最优排序问题,给出寻找工件最优排序的方法及实例说明。