原始工件的完工时间限制下的最小化最大延误时间的重新排序

考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决.     

混沌神经网络优化算法用于求解无等待流水调度问题的最小最大完工时间

利用李小平等提出的相邻工件加工结束时间差矩阵,将求解无等待流水调度问题的最小最大完工时间(Makespan)问题映射为TSP问题,构造对应的能量函数,进而得到随机混沌神经网络(SCSA)算法.实验结果证明该混沌神经网络优化算法优于RAJ算法和GANRAJ算法.     

Pm‖Cmax问题的算法AKK的一个改进的最坏情况性能比

本文考虑的是平行机排序问题Pm‖Cmax.对此问题Knuth和Kleitman给出了一个近似算法AKK,Graham证明了此算法的最坏情况性能比不大于1＋1-1/m/1＋｜k/m｜,而且当k≡0（modm）时这个界是紧的.在本文中我们给出了此算法的一个改进的最坏情况性能比： 1＋max{1-1/m/1＋k1＋1/m,1-1/m-k2/1＋k1},其中k1和k2为非负整数且k1m＋k2=k.本文证明了当k2≠0时,它好于Graham的结果,同时我们给出了两个实例说明这个界是紧的.     

含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性

本文研究含有批处理机的三台机器流水作业加工总长问题在某些情形下的计算复杂性。在批处理机上同时加工的工件组成一个工件批，一个工件批的所有工件同时开始、同时结束。当批处理机的容量有限时，我们证明了下列情形为强NP困难的：第一台机器是批处理机、其余两台机器是单机；第二台机器是单机、其余两台机器是批处理机；第三台机器是批处理机、其余两台机器是单机。     

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

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

重入排序问题综述

重入排序问题打破传统假设：工件在加工过程中不止一次地访问某台机器,是一种新型的排序问题. 重入的特点源于半导体生产, 并广泛存在于其他领域. 对重入排序问题已有文献中的成果进行梳理和分析,按问题所处机器环境的不同, 对内容和方法进行分类介绍和总结：包括单机问题、流水作业问题、混合流水作业问题及其他机器环境下的重入排序问题. 最后展望未来的趋势和研究方向.     

工件加工时间是开工时间线性函数的单机排序问题

研究了具有线性恶化工件的单机排序问题,其中线性恶化工件指的是工件的加工时间是开工时间的线性增长函数.在一般情况下,对目标函数为极小化完工时间平方和与极小化总误工数问题分别给出了最优算法.此外,在分段情况下,对目标函数为极小化最大完工时间问题也给出了最优算法.     

机器和工人都有加工资质约束的平行机排序问题研究

研究一类新型的平行机排序问题, 即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下, 如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_max. 将研究工件加工时间均为单位时间的情况, 通过建立网络流模型以及采用二分搜索技术, 可以在多项式时间内精确地求解上述问题, 算法复杂度为O(n^{3}logn). 同时提供了一种基于双重动态柔性选择\,(DDFS)\,策略的启发式算法,可以获得较好的排序效果, 算法复杂度为O(n^{2}).     

柔性工期下的资源受限项目调度双目标优化研究

在项目调度过程中,活动工期应根据项目截止工期以及资源供给情况进行合理设置,而在传统的资源受限项目调度问题(RCPSP)中,活动的工期往往是已知且固定的,这在一定程度上限制了项目调度的灵活性。多模式下的项目调度方式虽然弥补了这一缺点,但其提供的工期-资源组合种类固定且有限,并不一定能保证包含最优的工期-资源组合。本文将活动工期作为项目调度问题的决策变量,允许其在一定范围内取值。这种柔性工期调度方式虽然增加了项目调度难度,但提高了项目调度灵活性,同时可以起到压缩项目完工时间的作用。为验证柔性工期调度方式对项目工期和成本的影响,本文建立了工期-成本双目标权衡优化模型,设计了两阶段嵌套算法(NSGAⅡ-RS)对其求解,实验证明,柔性工期调度策略是一种鲁棒性较好的项目完工时间压缩策略。     

具有学习效应的两台机上最优混合流水作业算法

研究相同工件在两台机器（分别称为机器M₁和M₂）上的混合流水作业问题,每个给定工件有两个任务,分别称之为任务A和任务B,任务B只能在任务A完工后才能开始加工,每个工件有两种加工模式供选择：模式1是将两个任务都安排在机器M₂上加工;模式2是将任务A和B分别安排在机器M₁和M₂上加工.假设在加工工件时,机器具有学习效应,即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况,两种情况下都得到了最优算法.