双目标可重入混合流水车间调度问题的离散灰狼优化算法

可重入混合流水车间调度问题普遍存在于许多高科技制造产业中,如半导体晶圆制造和TFT-LCD面板生产过程等,但目前关于可重入调度问题的相关研究还比较少。本文设计了一种改进多目标灰狼优化算法(IMOGWO)解决最小化最大完工时间和总拖期时间最小的可重入混合流水车间调度问题,针对该问题特点对基本灰狼优化算法进行了一系列改进操作。通过对小规模测试问题基准算例的数值实验,验证了所设计的IMOGWO算法求解该调度问题的有效性。实验结果表明IMOGWO算法在非劣解的收敛性和支配性方面显著优于已有的NSGA-II和MOGWO算法,在解的分布性指标方面IMOGWO稍微优于其他两种算法。     

改进的布谷鸟算法求解考虑运输时间的分布式柔性流水车间调度问题

针对分布式制造环境下多车间调度问题特点,结合企业实际生产情况,考虑相邻工序间的运输时间,建立以最小化最大完工时间为优化目标的分布式柔性流水车间调度模型,提出一种改进布谷鸟算法用于求解该模型。算法改进包括设计了一种基于工序、车间和机器的三层编码方案;根据问题特点设计了混合种群初始化策略以提高种群质量;改进了布谷鸟搜索操作使其适用于求解该模型;设计了一种种群进化策略以提高算法收敛速度及解的质量。最后通过仿真实验,与多种算法对比,验证所提算法的有效性和优越性。     

具有机器适用限制的分布式置换流水车间问题的模型与算法

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.     

粒子群遗传混合算法求解考虑传输时间的FJSP

在某些生产制造场景中,工件在不同机器间的传输时间对车间调度的总拖期具有重要影响,本文基于此扩展了总拖期最小的柔性作业车间调度模型。针对问题模型的复杂性,采用粒子群优化算法和遗传算法的混合算法进行求解。在初始化过程以一定概率优选加工时间和传输时间短的机器并排除调度频繁的机器,使种群在保持多样性的前提下尽量选择优化结果好的个体;采用线性调整的方式动态改变交叉概率和变异概率的值,使种群在遗传算法的不同阶段具有不同的搜索强度;采用粒子群优化算法进行局部搜索,弥补了遗传算法局部搜索能力的不足。最后采用本文方法和其他方法求解柔性作业车间调度问题实例,并对比不同水平层次传输时间下的总拖期,验证了本文方法的有效性。     

考虑序列设置时间的混合流水车间多目标调度研究

基于混合流水车间多品种的特性,序列设置时间和工序跳跃是很多车间在调度时需要考虑的两个重要问题,论文充分考虑这两种生产约束,建立了以最大完工时间和负荷均衡指标为双目标的混合流水车间多目标调度数学模型,并运用改进的NSGA-II算法对基于实际企业生产数据假设的算例进行仿真求解,结果表明求解的调度方案符合实际需求,能够为企业的实际调度提供有效的方案。     

带有外包考虑的两阶段流水车间生产调度优化问题

将外包引入传统的生产调度优化问题,针对包括自产车间和外包车间在内的两阶段流水车间,考虑自产车间的定修、外包基于批次的运输以及外包车间的变动加工成本等因素,以最小化自产/外包总工期与最小化总成本为目标,构建混合整数非线性规划模型,解决包括加工任务分派、自产与外包各自的加工次序在内的生产调度优化问题。鉴于其属于NP-hard问题,设计了基于规则的启发式算法求解。最后运用数值实验验证了算法的有效性,并从运作管理的视角分析外包资源对生产系统的影响,进而对带有外包的调度优化策略与主要参数进行了敏感性分析。     

基于混沌量子算法和MAGTD的多目标FJSP求解策略

针对多目标环境下柔性作业车间的调度问题,以最小化最大完工时间和惩罚值为目标,建立调度问题的数学模型,提出了基于混沌理论的量子粒子群算法。针对实际生产交货期不确定的特点,在量子粒子群算法基础上,提出引入混沌机制建立初始群的方法;利用混沌机制的遍历性,提出混沌局部优化策略;为获取最优调度方案提出了引入多指标加权灰靶选择策略。通过典型基准算例和对比测试,验证了所提出的算法获得最满意调度方案的可行性和求解多目标柔性作业车间调度问题的有效性。     

基于异步次梯度法的LR算法及其在多阶段HFSP的应用

为降低求解复杂度和缩短计算时间,针对多阶段混合流水车间总加权完成时间问题,提出了一种结合异步次梯度法的改进拉格朗日松弛算法。建立综合考虑有限等待时间和工件释放时间的整数规划数学模型,将异步次梯度法嵌入到拉格朗日松弛算法中,从而通过近似求解拉格朗日松弛问题得到一个合理的异步次梯度方向,沿此方向进行搜索,逐渐降低到最优点的距离。通过仿真实验,验证了所提算法的有效性。对比所提算法与传统的基于次梯度法的拉格朗日松弛算法,结果表明,就综合解的质量和计算效率而言,所提算法能在较短的计算时间内获得更好的近优解,尤其是对大规模问题。     

求解柔性作业车间调度的动态群智能优化算法

针对柔性作业车间调度问题,提出一种新型两阶段动态混合群智能优化算法.算法初始阶段采用动态邻域的协同粒子群进行粗搜索,第二阶段提出了基于混沌算子的蜂群进行细搜索,既增强了种群多样性,又提高了算法搜索精度,实现了全局搜索与局部搜索能力的有效平衡.针对柔性作业车间调度问题特点,采用独特的编码方式和位置更新策略来避免不合法解的产生.最后将此算法在不同规模的实例上进行了仿真测试,并与最近提出的其他几种具有代表性的算法进行了比较,验证了算法的有效性和优越性.     

建筑废料现场分拣协调调度优化研究

工程项目施工现场废料分拣的效率对施工进度具有重要的影响。通过分析现场废料分拣实施过程,建立了带有限中间缓冲的混合流水车间调度模型。提出了收集阶段作业排序的动态自适应算法和后续设备分配问题的考虑缓冲区的设备分配规则,在此基础上设计了废料分拣模型的启发式算法,平衡各分区工作量,进一步搜索最优解,并推导了问题的一个低界。实验结果表明,所提出算法能很好地对施工现场废料分拣问题进行求解,具有良好的收敛性和较高的时间效率。     

A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities

This paper presents a novel discrete artificial bee colony (DABC) algorithm for solving the multi-objective flexible job shop scheduling problem with maintenance activities. Performance criteria considered are the maximum completion time so called makespan, the total workload of machines and the workload of the critical machine. Unlike the original ABC algorithm, the proposed DABC algorithm presents a unique solution representation where a food source is represented by two discrete vectors and tabu search (TS) is applied to each food source to generate neighboring food sources for the employed bees, onlooker bees, and scout bees. An efficient initialization scheme is introduced to construct the initial population with a certain level of quality and diversity. A self-adaptive strategy is adopted to enable the DABC algorithm with learning ability for producing neighboring solutions in different promising regions whereas an external Pareto archive set is designed to record the non-dominated solutions found so far. Furthermore, a novel decoding method is also presented to tackle maintenance activities in schedules generated. The proposed DABC algorithm is tested on a set of the well-known benchmark instances from the existing literature. Through a detailed analysis of experimental results, the highly effective and efficient performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature.     

Hybrid flowshop scheduling with machine and resource-dependent processing times

Most of research in production scheduling is concerned with the optimization of a single criterion. However the analysis of the performance of a schedule often involves more than one aspect and therefore requires a multi-objective treatment. In this research, with combination of two multiple objective decision-making methods, min–max and weighted techniques, a new solution presentation method and a robust hybrid metaheuristic, we solved sequence-dependent setup time hybrid flowshop scheduling problems. In this paper for reflecting real-world situation adequately, we assume the processing time of each job depends on the speed of machine and amount of resource allocated to each machine at the stage which is processed on it. In formulation of min–max type, the decision-maker can have the flexibility of mixed use of weights and distance parameter in expressing desired improvement on produced Pareto optimal solutions. To minimize makespan and total resource allocation costs, the proposed hybrid approach is robust, fast, and simply structured, and comprises two components: genetic algorithm and a variable neighborhood search. The comparison shows the proposal to be very efficient for different structure instances.     

Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time

This study considers a hybrid assembly-differentiation flowshop scheduling problem (HADFSP), in which there are three production stages, including components manufacturing, assembly, and differentiation. All the components of a job are processed on different machines at the first stage. Subsequently, they are assembled together on a common single machine at the second stage. At the third stage, each job of a particular type is processed on a dedicated machine. The objective is to find a job schedule to minimize total flow time (TFT). At first, a mixed integer programming (MIP) model is formulated and then some properties of the optimal solution are presented. Since the NP-hardness of the problem, two fast heuristics (SPT-based heuristic and NEH-based heuristic) and three hybrid meta-heuristics (HGA-VNS, HDDE-VNS and HEDA-VNS) are developed for solving medium- and large-size problems. In order to evaluate the performances of the proposed algorithms, a lower bound for the HADFSP with TFT criteria (HADFSP-TFT) is established. The MIP model and the proposed algorithms are compared on randomly generated problems. Computational results show the effectiveness of the MIP model and the proposed algorithms. The computational analysis indicates that, in average, the HDDE-VNS performs better and more robustly than the other two meta-heuristics, whereas the NEH heuristic consume little time and could reach reasonable solutions.     

A note on scheduling flowshops with flexible stage ordering

We develop an asymptotically optimal heuristic for the m-stage flowshop problem with flexible stage ordering. Our algorithm supplies a job permutation which has the same worst case absolute bound for all possible m! orderings of the m stages. The development of our algorithm is motivated by the observation that it is sometimes beneficial to reverse the processing order in multi-stage manufacturing processes. Our algorithm facilitates the development of a job sequence a priori before the processing order is determined.     

No-wait flexible flowshop scheduling with no-idle machines

This paper considers a two-stage flexible flowshop scheduling problem with no waiting time between two sequential operations of a job and no idle time between two consecutive processed jobs on machines of the second stage. We show its complexity and present a heuristic algorithm with asymptotically tight error bounds.     

A two-machine flowshop scheduling problem with a truncated sum of processing-times-based learning function

Scheduling with learning effects has received continuing attention in the recent days. However, it can be found that the actual processing time of a given job drops to zero precipitously as the job has a big processing time or the number of jobs increases. Moreover, most researchers paid more attention to single-machine settings, and the flowshop settings then are relatively unexplored. Motivated by these observations, we consider a two-machine total completion time flowshop problem in which the actual job processing time is a function depending on the jobs that have already been processed and a control parameter. In this paper, we develop a branch-and-bound and a genetic heuristic-based algorithm for the problem. In addition, the experimental results of all proposed algorithms are also provided.     

A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion

In this paper, we present a discrete artificial bee colony algorithm to solve the no-idle permutation flowshop scheduling problem with the total tardiness criterion. The no-idle permutation flowshop problem is a variant of the well-known permutation flowshop scheduling problem where idle time is not allowed on machines. In other words, the start time of processing the first job on a given machine must be delayed in order to satisfy the no-idle constraint. The paper presents the following contributions: First of all, a discrete artificial bee colony algorithm is presented to solve the problem on hand first time in the literature. Secondly, some novel methods of calculating the total tardiness from makespan are introduced for the no-idle permutation flowshop scheduling problem. Finally, the main contribution of the paper is due to the fact that a novel speed-up method for the insertion neighborhood is developed for the total tardiness criterion. The performance of the discrete artificial bee colony algorithm is evaluated against a traditional genetic algorithm. The computational results show its highly competitive performance when compared to the genetic algorithm. Ultimately, we provide the best known solutions for the total tardiness criterion with different due date tightness levels for the first time in the literature for the Taillard’s benchmark suit.     

Memetic algorithm based on marriage in honey bees optimization for flexible job shop scheduling problem

This paper proposes a new memetic algorithm based on marriage in honey bees optimization (MBO) algorithm for solving the flexible job shop scheduling problem. The proposed algorithm introduces four new features to the standard MBO algorithm, mainly to get the search to move away from the local optimum: (1) the use of a harmony memory to improve the quality of initial population; (2) the introduction of a new crossover operator called triparental crossover to help increase the genetic diversity in the offspring; (3) the addition of adaptive crossover probability (\(\hbox {P}_{\mathrm{c}})\) and mutation probability (\(\hbox {P}_{\mathrm{m}})\) to remove the need for users to specify these probabilities; and (4) the incorporation of simulated annealing algorithm embedded with a set of heuristics to enhance the local search capability. The proposed algorithm was evaluated and compared to several state-of-the-art algorithms in the literature. The experimental results on five sets of standard benchmarks show that the proposed algorithm is very effective in solving the flexible job shop scheduling problems.     

工件优先级图为非连接图且含环的单机总加权拖期调度问题

为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。     

Scheduling dynamic hybrid flowshop with serial batching machines

This paper considers a multi-stage dynamic hybrid flowshop in which some stage contains several identical batching machines and the other stages contain several identical discrete machines. Each discrete machine can process no more than one operation at a time, and each batching machine can process several jobs continuously in a batch. This problem has a strong practical background in the process industry. Since the problem is NP-hard, improved Lagrangian relaxation (LR) is developed where batch decomposition strategy is applied and mixed backward and forward dynamic programming is designed to solve batch-level subproblems with the case that each operation may have multiple predecessors and successors. Results of numerical experiments with up to 60 jobs show that the proposed algorithm can obtain better solutions in a reasonable computation time than traditional LR.