具有恶化效应和学习效应的单机成组调度问题

讨论了一类具有恶化效应和学习效应的单机成组调度问题, 其中工件的加工时间为开工时间和组内工序的函数. 通过对问题性质的分析以及多项式时间算法的描述, 得出如下结论: 在单机成组调度问题中, 即便工件的加工时间同时受恶化效应和学习效应的制约, 极小化完工时间问题以及极小化总资源消耗的问题仍是多项式时间可解的.     

应用萤火虫算法求解基于学习效应的PFSP问题

针对置换流水车间调度问题,应用学习效应理论,将工件的加工时间与工件的加工位置建立联系,缩短了工件的最大完工时间,并将不同学习率下的最小化最大完工时间进行比较,给生产制造企业合理安排生产计划提供借鉴。应用MATLAB软件编写萤火虫算法,对建立的模型进行仿真测试,通过与粒子群算法和遗传算法进行结果对比,验证了算法的有效性,在此基础上求解出具有不同学习率的置换流水车间调度问题的最小化最大完工时间。     

多AGV和机器集成的多目标柔性作业车间调度研究

为解决智能制造环境中具有多时间和多AGV约束的柔性作业车间调度问题,构建了以最小化最大完工时间、最小化总延期、最小化设备总负荷为目标的机器/AGV双约束多目标调度模型,模型中综合考虑加工时间、工件到达时间、交货期等多时间因素,进行了多AGV和机器集成调度。为求解该模型,设计了新的AGV调度规则和改进的NSGA-算法,算法中提出了基于工序的扩展染色体编码方式和基于AGV分配的贪婪式解码策略,同时设计了不同参数控制的多种群二元锦标赛选择和分段交叉变异策略以及基于Pareto级的去重精英保留策略,以促进个体协同优化搜索。通过实例实验,分析了不同AGV数量任务分配方案下的模型有效性,对4个案例的仿真测试和同类算法比较解也验证了改进NSGA-算法求解该模型的有效性。     

基于改进NSGA-Ⅱ的考虑自动引导车充电策略的集成调度

针对自动引导车（AGV）在自动化集装箱码头（ACT）执行任务过程中的电量问题，提出基于改进的非支配排序遗传算法-Ⅱ（NSGA-Ⅱ）的考虑AGV充电策略的集成调度。首先，在岸桥、场桥和AGV集成调度模式下，考虑AGV在不同作业状态下的耗电量，并建立以最小化作业完工时间和总耗电量为目标的多目标混合规划模型；其次，为提高传统NSGA-Ⅱ的性能，设计自适应NSGA-Ⅱ，并将所提算法与CPLEX求解器、NSGA-Ⅱ和多目标粒子群优化（MOPSO）算法进行性能对比；最后，设计AGV不同充电策略并对设备数量配比进行实验研究。算法对比实验结果表明：相较于传统NSGA-Ⅱ算法，自适应NSGA-Ⅱ对双目标的优化分别提升了2.8%和2.63%。利用自适应NSGA-Ⅱ进行的充电策略和设备数量配比实验的结果表明：增加AGV充电次数能够减少AGV的充电时间，且调整设备数量配比至3∶3∶9和3∶7∶3时，场桥和AGV的时间利用率分别达到最高。可见，AGV充电策略及设备数量配比对码头多设备集成调度有一定影响。     

用于求解单机调度问题的混合禁忌搜索算法

针对工件不同释放时间和实际加工时间之和的学习效应情况,研究单机调度总完工时间最小化问题。根据问题的NP-hard特性,证明2个优先规则,结合禁忌搜索算法与优先规则,提出一个混合禁忌搜索算法,提高了算法跳出局部最优的能力,既保留了优异的基因又扩大了领域的搜索范围。实验结果表明,与基准算法相比,该算法在求解质量上有更好的表现,而且随着工件规模的增加优势更加明显。     

到达时间依赖于资源分配的单机排序问题*

研究了具有线性退化及学习效应作用下的单机排序问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下最大完工时间极小化问题,给出了相应的最优算法;也考虑了满足工件最大完工时间限制的条件下极小化资源消耗的总量问题,提出最优资源分配方案。     

同时具有学习和遗忘效应的TFT-LCD模块组装调度问题研究

薄膜晶体管液晶显示器（TFT-LCD）制造过程特点包含三个部分：前段阵列（Array）过程、后段面板成盒（Cell）过程、模块组装（Module）过程。针对薄膜晶体管液晶显示器模块组装生产规模性、精密性、重复性的特点,引入相关工件学习效应和遗忘效应,以极小化工件最大工件完工时间为目标,讨论TFT-LCD模块组装调度问题。采用新型的布谷鸟智能优化算法对当前模型进行求解,通过对算法进行模拟仿真实验,验证了布谷鸟算法在求解模块调度问题上的有效性和可行性。此外,针对学习效应和遗忘效应对模块组装调度的影响,提出了相应的调度建议,为薄膜晶体管液晶显示器的研究和实际生产提供了参考。     

考虑恶化效应的MapReduce模型下的同类机调度

本文研究了MapReduce模型中考虑恶化效应的同类机调度问题. 在MapReduce模型中每个工件加工必须经 过两道工序. 其中在第1道工序中每个工件加工任务可分割成若干个子任务且能并行加工, 当某个工件中的所有子 任务全部完成后, 才允许启动第2道工序, 且第2道工序只能在一台机器上连续加工. 本文考虑了工件实际加工时间 与其开工前的等待时间呈线性函数关系的恶化效应, 构建了以最小化所有工件的逗留时间和为目标函数的混合整 数规划模型, 同时给出了问题的一个下界, 最后设计了采用正余弦差分扰动机制的改进蝙蝠优化算法来求解模型. 通过数值仿真对蝙蝠优化算法、遗传算法、CPLEX结果与下界进行对比, 验证了模型的正确性和改进算法的有效 性.     

自动化码头考虑缓冲区的设备协调调度优化

为研究自动化码头缓冲区的设置对装卸设备作业协调性的影响,针对“双小车岸桥+AGV+缓冲支架+自动化轨道吊”的装卸工艺,利用缓冲有限的柔性流水车间调度理论建立集成调度优化模型,设计了以NEH启发式算法产生初始解的遗传算法对模型进行求解,得出相应的设备调度优化方案与完工时间,并通过对比遗传算法与粒子群算法的运算结果验证了提出的模型与算法的有效性,进而分析了不同缓存区容量对完工时间以及设备使用率的影响。结果表明,设置缓冲区能有效提高不同设备之间的作业协调性,显著减少AGV的使用数量与作业完工时间。     

考虑学习效应的最小化延误总时间的单机批次排序问题

一些生产场景中,工件以批次作业的形式被安排生产,工件批量大、加工工序基本相同,所以标准工时相同,而且实际加工时间会受到学习效应的影响.为此,讨论学习效应的最小化延误总时间的单机批次排序问题,对该问题建立数学模型.该问题属于NP-hard问题,采用动态规划算法(DP)和模拟退火算法(SA)求解该问题,通过实验分析不同规模时DP的执行时间与SA的执行时间和求解误差的变化趋势,比较SA与其他实践中常用的经典规则的求解效果.最后得出DP适合批次数小于13的小规模问题,可以得到精确解;与经典规则相比,SA至少可以使目标函数降低20%,表明SA算法具有有效性.SA解决大规模问题时效果较优,并得出SA的执行时间和误差随着控制参数改变的变化趋势.     

具有行为效应的TFT-LCD模块组装多目标调度研究

为了优化调度方案,针对最小化最大完成时间、机器总空闲时间和工件总延期时间的具有学习退化效应的TFT-LCD模块组装多目标调度问题,提出改进混沌烟花算法。基于两段式编码,结合加工时间优先选择及动态淘汰锦标赛规则构建帕累托非劣解集。仿真实验表明：改进烟花算法求解质量优于烟花算法、粒子群算法,学习退化效应增强将减少可行解数量,学习率、退化因子增大使得非劣解远离原点。     

The common due-date early/tardy scheduling problem on a parallelmachine under the effects of time-dependent learning and linear and nonlinear deterioration

This paper considers earliness/tardiness (ET) scheduling problem on a parallel machine environment with common due-date under the effects of time-dependent learning and linear and nonlinear deterioration. In this paper, the effects of learning and deterioration are considered simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. This study shows that optimal solution for ET scheduling problem under effects of learning and deterioration is V-shape schedule under certain agreeable conditions. Furthermore, we present a mathematical model for the problem under study and an algorithm for solving large test problems. The algorithm can solve problems of 1000 jobs and four machines within 3 s on average.     

自动化码头AGV充电与作业的集成调度研究

为了提高自动化集装箱码头AGV（Automated Guided Vehicle）的作业效率,根据采用电力驱动的AGV作业时的充电需求和运输过程的特性,考虑了垂岸式集装箱堆场布局和AGV充电过程对实际作业的影响,以最大化AGV充电利用率、最小化最末任务完成时间、最小化AGV空载时间为目标,以AGV充电后的续航能力等为约束条件,以遗传算法为研究方法,构建了考虑充电过程的自动化码头AGV作业的调度模型。通过算例分析,对比了遗传算法与混合整数规划算法的求解效果,分析了参与运输的AGV数量对运输时间的影响,也验证了遗传算法给出的调度方案的可信性。最后得出结论：针对该问题,遗传算法可以快速、高效地给出值得信赖的AGV调度方案。     

Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration

This paper considers a parallel machine earliness/tardiness (ET) scheduling problem with different penalties under the effects of position based learning and linear and nonlinear deterioration. The problem has common due-date for all jobs, and effects of learning and deterioration are considered simultaneously. By the effects of learning we mean that the job processing time decreases along the sequence of partly similar jobs, and by the effects of deterioration we mean slowing performance or time increases along the sequence of jobs. This study shows that optimal solution for ET scheduling problem under effects of learning and deterioration is V-shape schedule under certain agreeable conditions. Furthermore, we design a mathematical model for the problem under study and algorithm and lower bound procedure to solve larger test problems. The algorithm can solve problems of 1000 jobs and four machines within 3 s on average. The performance of the algorithm is evaluated using results of the mathematical model.     

基于深度强化学习求解作业车间机器与 AGV联合调度问题

针对作业车间中自动引导运输车(automated guided vehicle, AGV)与机器联合调度问题,以完工时间最小化为目标,提出一种基于卷积神经网络和深度强化学习的集成算法框架.首先,对含AGV的作业车间调度析取图进行分析,将问题转化为一个序列决策问题,并将其表述为马尔可夫决策过程.接着,针对问题的求解特点,设计一种基于析取图的空间状态与5个直接状态特征;在动作空间的设置上,设计包含工序选择和AGV指派的二维动作空间;根据作业车间中加工时间与有效运输时间为定值这一特点,构造奖励函数来引导智能体进行学习.最后,设计针对二维动作空间的2D-PPO算法进行训练和学习,以快速响应AGV与机器的联合调度决策.通过实例验证,基于2D-PPO算法的调度算法具有较好的学习性能和可扩展性效果.     

考虑电池包数量的自动化集装箱码头多AGV调度优化

针对自动化集装箱码头自动引导小车（automated guided vehicle,AGV）的实际换电特性,为了降低AGV的总任务完成时间和换电总时间,合理规划换电站内的电池包数量,建立了双层规划模型。首先考虑AGV的电池续航、空重载SOC变化特性和不同剩余电量与速度变化,以降低AGV的总任务完成时间为目标,构建考虑换电的多AGV集装箱任务调度上层模型。在此基础上,为了合理规划换电站内的电池包数量,考虑自动化码头中换电站的实际电池包选取原则和换电流程,对换电站和电池包的选择进行决策,以降低换电总时间为目标,构建换电电池包配置下层模型。最后通过遗传算法分别对小规模和大规模算例进行求解。算例结果表明,此双层规划模型能够有效地减少总任务完成时间和换电总时间,提高了6.46%的AGV利用率,减少了23.1%的换电站电池包数量。     

Some scheduling problems with deteriorating jobs and learning effects

Although scheduling with deteriorating jobs and learning effect has been widely investigated, scheduling research has seldom considered the two phenomena simultaneously. However, job deterioration and learning co-exist in many realistic scheduling situations. In this paper, we introduce a new scheduling model in which both job deterioration and learning exist simultaneously. The actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled position. For the single-machine case, we derive polynomial-time optimal solutions for the problems to minimize makespan and total completion time. In addition, we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain agreeable conditions. For the case of an m-machine permutation flowshop, we present polynomial-time optimal solutions for some special cases of the problems to minimize makespan and total completion time.     

Two-machine flow shop problem with effects of deterioration and learning

In this paper we consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions.     

Single-machine scheduling problems with deteriorating jobs and learning effects

In this paper, we introduce a new scheduling model in which deteriorating jobs and learning effect are both considered simultaneously. By deterioration and the learning effect, we mean that the actual processing time of a job depends not only on the processing time of the jobs already processed but also on its scheduled position. For the single-machine case, we show that the problems of makespan, total completion time and the sum of the quadratic job completion times remain polynomially solvable, respectively. In addition,we show that the problems to minimize total weighted completion time and maximum lateness are polynomially solvable under certain conditions.     

One-machine scheduling problems with deteriorating jobs and position-dependent learning effects under group technology considerations

In this paper, we introduce a group scheduling model with general deteriorating jobs and learning effects in which deteriorating jobs and learning effects are both considered simultaneously. This means that the actual processing time of a job depends not only on the processing time of the jobs already processed, but also on its scheduled position. In our model, the group setup times are general linear functions of their starting times and the jobs in the same group have general position-dependent learning effects and time-dependent deterioration. The objective of scheduling problems is to minimise the makespan and the sum of completion times, respectively. We show that the problems remain solvable in polynomial time under the proposed model.