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

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

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

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

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

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

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

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

求解零等待流水车间调度问题的改进蝙蝠算法

针对零等待流水车间调度问题特性,设计了一种蝙蝠算法进行求解.算法模拟蝙蝠捕食搜索行为进行寻优,利用基于最小位置值规则的随机键编码方式来表示问题解,采用基于NEH方法的局部搜索策略和随机交换、插入、逆序操作的变邻域搜索策略来提高局部优化性能,进一步根据Metropolis概率准则接受劣解来避免早熟.通过典型算例对所提算法进行仿真测试并与粒子群算法和RAJ启发式算法进行对比,结果表明所设计算法求解零等待流水车间调度问题的有效性和优越性,是求解流水车间生产调度问题的一种有效工具.     

具有学习效应的置换流水车间调度问题布谷鸟搜索算法求解

对于以最小化最大完工时间为目标的置换流水车间调度问题,现有研究较少考虑学习效应对生产调度的影响,构建了具有学习效应的PFSP问题数学模型.采用ROV的编码方式,应用布谷鸟搜索算法进行离散优化问题求解.通过对Car类问题的大量仿真测试,表明了布谷鸟搜索算法求解该类问题的可行性和有效性.同时,证明了学习效应能够降低最大完工时间,从而提高生产效率.     

考虑机器调整次数和产品质量的卷烟批量计划和柔性流水车间调度集成问题

针对卷烟企业生产中的批量计划和柔性流水车间调度集成问题,构建了整数规划模型,目标函数由卷烟生产时间、生产线调整次数、卷烟质量、库存成本四部分组成。鉴于该问题的NP-hard性,设计遗传算法进行求解,通过合理设计遗传算子,避免不可行解出现。应用某卷烟企业数据得到优化排产结果,与该企业之前依照经验排产方案进行对比,发现优化排程结果在减少品牌转换次数,提高生产的连续性方面具有明显优势。该算法已作为某卷烟企业排产人员的排产参考,应用于排产决策中,取得了良好的效果,对卷烟企业制定排产计划具有一定的实际指导意义。     

模糊置换流水车间调度的多目标模型

为了求解同时考虑模糊加工时间和模糊交货期的多目标置换流水车间调度问题,提出一种模糊多目标调度模型。针对目标之一的最大化满意度,考虑决策者偏好,建立基于悲观准则的偏好满意度模型,并在此基础上,兼顾考虑可信度,对满意度模型进行改进;针对Pareto最优解的选取,引入模糊集理论和概率论,运用面积补偿法将最大模糊完工时间去模糊化,便于可行解之间进行比较。最后,采用随机系列算例以及典型算例进行优化计算,计算结果验证了模型的有效性。     

改进果蝇算法求解带有学习效应的PFSP

对基本果蝇算法进行改进,求解基于工件分类的带有学习效应的置换流水车间问题.改进算法的编码方式以及搜索机制,将转移概率矩阵运用到果蝇寻优过程中.经测试实验表明,改进后的果蝇算法在寻优速度以及寻优率上较其他算法有着较明显的优势.另根据工件的相似度对生产工件进行分类,提出了基于聚类距离的置换流水车间学习效应模型,用改进的果蝇算法对其模型进行求解,分析了不同学习率和聚类距离对完工时间的影响,一方面验证了算法的有效性,另一方面说明了学习效应对企业生产调度有一定影响.     

基于Epsilon约束法的短纤维生产调度的双目标优化研究

针对短纤维生产行业实际,本文综合考虑客户的需求差异、客户的重要程度、纤维生产设备的准备时间以及交货期差异等因素,研究连续需求下的短纤维生产排序优化问题。首先,本文建立双目标整数规划模型,即最小化客户订单总延迟和最小化机器总准备时间;其次,设计Epsilon约束算法并调用CPLEX精确求解调度方案,即帕累托前沿;最后设计非支配排序的遗传算法(NSGA-II)求解大规模生产下的调度优化方案。通过实验,证明该整数规划模型和算法对解决多客户连续需求问题具有实际价值,进而可以为短纤维生产企业提供参考。     

阻塞混流生产机器人制造单元调度问题可行解性质研究

针对阻塞混流生产机器人制造单元调度问题的可行解性质进行研究。首先,定义了机器人活动,将机器人运行排序和工件加工排序转化为机器人活动调度,将二维调度问题转化为一维调度问题;其次,提出了可行机器人活动调度概念,给出了几个等价定义;最后,给出了可行机器人活动调度经过一定变换,仍然是可行调度的条件。这些性质为优化算法的设计提供了理论基础。     

Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage

This paper considers a scheduling problem in two-stage hybrid flow shop, where the first stage consists of two machines formed an open shop and the other stage has only one machine. The objective is to minimize the makespan, i.e., the maximum completion time of all jobs. We first show the problem is NP-hard in the strong sense, then we present two heuristics to solve the problem. Computational experiments show that the combined algorithm of the two heuristics performs well on randomly generated problem instances.     

混合无等待流水线干扰管理调度方法研究

针对带分批约束的混合无等待流水加工环境中干扰事件的出现导致初始调度计划发生偏离的问题,研究如何运用干扰管理理论来应对工件变更扰动情况,建立了兼顾最小化工件完工时间加权和指标(初始调度目标)和最小化工件完工滞后时间加权和指标(偏离校正目标)的干扰管理调度模型,提出了双层微粒群优化策略与随机多邻域搜索机制相结合的混合求解算法。数值算例仿真实验结果表明,包含“插入-交换”大概率邻域搜索算子的混合微粒群优化算法求解本文所构建的干扰管理调度模型是有效的。     

Flow shop scheduling jobs with position-dependent processing times

The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown.     

Research on permutation flow shop scheduling problems with general position-dependent learning effects

Machine learning exists in many realistic scheduling situations. This study focuses on permutation flow shop scheduling problems, where the actual processing time of a job is defined by a general non-increasing function of its scheduled position, i.e., general position-dependent learning effects. The objective functions are to minimize the total completion time, the makespan, the total weighted completion time, and the total weighted discounted completion time, respectively. To solve these problems, we present approximation algorithms based on the optimal permutations for the corresponding single machine scheduling problems and analyze their worst-case error bound.     

Flow shop scheduling with heterogeneous workers

We propose an extension to the flow shop scheduling problem named Heterogeneous Flow Shop Scheduling Problem (Het-FSSP), where two simultaneous issues have to be resolved: finding the best worker assignment to the workstations, and solving the corresponding scheduling problem. This problem is motivated by Sheltered Work centers for Disabled, whose main objective is the labor integration of persons with disabilities, an important aim not only for these centers but for any company desiring to overcome the traditional standardized vision of the workforce. In such a scenario the goal is to maintain high productivity levels by minimizing the maximum completion time, while respecting the diverse capabilities and paces of the heterogeneous workers, which increases the complexity of finding an optimal schedule. We present a mathematical model that extends a flow shop model to admit a heterogeneous worker assignment, and propose a heuristic based on scatter search and path relinking to solve the problem. Computational results show that this approach finds good solutions within a short time, providing the production managers with practical approaches for this combined assignment and scheduling problem.     

Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with a general position-dependent learning effects. By the general position-dependent learning effects, we mean that the actual processing time of a job is defined by a general non-increasing function of its scheduled position. The objective is to minimize one of the five regular performance criteria, namely, the total completion time, the makespan, the total weighted completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems. We also analyze the worst-case bound of our heuristic algorithms.     

Local search algorithms for the multiprocessor flow shop scheduling problem

The multiprocessor flow shop scheduling problem is a generalization of the ordinary flow shop scheduling problem. The problem consists of both assigning operations to machines and scheduling the operations assigned to the same machine. We review the literature on local search methods for flow shop and job shop scheduling and adapt them to the multiprocessor flow shop scheduling problem. Other local search approaches we consider are variable-depth search and simulated annealing. We show that tabu search and variable-depth search with a neighborhood originated by Nowicki and Smutnicki outperform the other algorithms.     

A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines

We study the problem of minimizing the makespan in a two-stage assembly flow shop scheduling problem with uniform parallel machines. This problem is a generalization of the assembly flow shop problem with concurrent operations in the first stage and a single assembly operation in the second stage. We propose a heuristic with an absolute performance bound which becomes asymptotically optimal as the number of jobs becomes very large. We show that our results slightly improve earlier results for the simpler assembly flow shop problem (without uniform machines) and for the two-stage hybrid flow shop problem with uniform machines.     

A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations

A hybrid flow shop scheduling problem (HFSP) with assembly operations is studied in this paper. In the considered problem, a number of products of the same kind are produced. Each product is assembled using a set of several parts. At first, the parts are produced in a hybrid flow shop and then they are assembled in an assembly stage to produce products. The considered objective is to minimize the completion time of all products (makespan). This problem has been proved strongly NP-hard, so in order to solve it, a hierarchical branch and bound algorithm is presented. Also, some lower and upper bounds are developed to increase the efficiency of the proposed algorithm. The numerical experiments are used to evaluate the performance of the proposed algorithm.