Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach

In scheduling problems, taking the sequence-dependent setup times into account is one of the important issues that have recently been considered by researchers in the production scheduling field. In this paper, we consider flexible job-shop scheduling problem (FJSP) with sequence-dependent setup times to minimize makespan and mean tardiness. The FJSP consists of two sub-problems from which the first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on all machines. To solve this problem, a variable neighborhood search (VNS) algorithm based on integrated approach is proposed. In the presented optimization method, the external loop controlled the stop condition of algorithm and the internal loop executed the search process. To search the solution space, the internal loop used two main search engines, i.e. shake and local search procedures. In addition, neighborhood structures related to the sequencing problem and the assignment problem were employed to generate neighboring solutions. To evaluate the performance of the proposed algorithm, 20 test problems in different sizes are randomly generated. Consequently, computational results and comparisons validate the quality of the proposed approach.     

Comments on “An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems” [Comput. Ind. Eng. 48 (2005) 409–425]

An effective hybrid optimization approach proposed by Xia and Wu [Xia, W. J., Wu, Z. M. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48, 409–425] was recently published in Computers & Industrial Engineering journal to solve the multi-objective flexible job-shop scheduling problems. In this work, comments and suggestions are given to the recently published approach of Xia and Wu (2005). The comments like centralized the problem formulation and experimental comparison. The modification of the problem formulation is suggested in this work.     

求解柔性流水车间调度问题的高效分布估算算法

针对最小化最大完工时间的柔性流水车间调度,利用事件建模思想,线性化0-1混合整数规划模型,使得小规模调度问题通过Cplex可以准确求解,同时设计了高效分布估算算法来求解大规模调度问题.该算法采用的是一种新颖的随机规则解码方式,工件排序按选定的规则安排而机器按概率随机分配.针对分布估算算法中的概率模型不能随种群中个体各位置上工件的更新而自动调整的缺点,提出了自适应调整概率模型,该概率模型能提高分布估算算法的收敛质量和速度.同时为提高算法局部搜索能力和防止算法陷入局部最优,设计了局部搜索和重启机制.最后,采用实验设计方法校验了高效分布估算算法参数的最佳组合.算例和实例测试结果都表明本文提出的高效分布估算算法在求解质量和稳定性上均优于遗传算法、引力搜索算法和经典分布估算算法.     

Minimizing total completion time on a single machine with a flexible maintenance activity

A problem of jointly scheduling multiple jobs and a single maintenance activity on a single machine with the objective of minimizing total completion time is considered in this paper. It is assumed that the machine should be stopped for maintenance which takes a constant duration within a predefined period. The problem is generalized from the one with a fixed maintenance in that it relaxes the starting time of the maintenance from a fixed time point to a predefined period. Both resumable and nonresumable cases are studied. First, three properties of an optimal solution to each of the two cases are identified. Then it is shown that the proposed shortest processing time (SPT) algorithm is optimal for the resumable case. As for the nonresumable case, the conditions under which the SPT algorithm is optimal are also specified. Furthermore, it is shown that relaxing the starting time of the maintenance cannot improve the relative error bound of the SPT algorithm. The focus of the paper is presented afterwards, which is to develop a dynamic programming algorithm and a branch-and-bound algorithm to generate an optimal solution for this case. Experimental results show that these algorithms are effective and complementary in dealing with different instances of the problem.     

H.223协议实时处理中透明码生成的快速算法及其实现

本文给出了一种基于软件实现的透明码生成的快速算法。字节是Ｃ语言中所能处理的最小数据单元,因而对字节的处理（包括存取、运算等）有着位处理无法比拟的优点。根据这一特点,该算法以字节为单位,通过查表方式,快速生成（和还原）透明码。从而避免了以位操作所带来的时间开销较大的缺点     

关于车间调度优化问题的仿真与设计

研究多目标柔性车间调度优化问题.由于传统车间调度存在局限性,造成车间多目标调度优化困难.为此,结合实际生产过程的特点和约束条件,构建了以最大完工时间、加工成本为目标函数的柔性车间调度模型,提出了多种群自适应免疫遗传算法.在初始种群中采用多个种群同时进化,能够有效保持种群的多样性;在算法中将自适应策略用于免疫操作中,提出动态自适应提取疫苗,以提高算法的执行效率,使算法更具灵活性和自适应性.仿真结果表明,改进算法对大规模复杂问题具有搜索速度快、稳定性强的特点,提高了调度的效率.     

Integrated scheduling of resource-constrained flexible manufacturing systems using constraint programming

This contribution presents a novel approach to address the scheduling of resource-constrained flexible manufacturing systems (FMSs). It deals with several critical features that are present in many FMS environments in an integrated way. The proposal consists in a constraint programming (CP) formulation that simultaneously takes into account the following sub-problems: (i) machine loading, (ii) manufacturing activities scheduling, (iii) part routing, (iv) machine buffer scheduling, (v) tool planning and allocation, and (vi) AGV scheduling, considering both the loaded and the empty movements of the device. Before introducing the model, this work points out the problems that might appear when all these issues are not concurrently taken into account. Then, the FMS scheduling model is presented and later assessed through several case-studies. The proposed CP approach has been tested by resorting to problems that consider dissimilar number of parts, operations per part, and tool copies, as well as different AGV speeds. The various examples demonstrate the importance of having an integrated formulation and show the important errors that can occur when critical issues such as AGV empty movements are neglected.     

柔性作业车间调度中的组合遗传优化研究

针对柔性作业车间调度问题,提出一种组合遗传算法。该算法在种群初始化、选择、交叉、变异各阶段,组合使用各种不同的策略。针对机器编码部分的交叉,提出一种基于工件的机器交叉算子,用以改进机器分配部分随机交叉引起的对父代优秀基因继承不足的缺陷。通过对典型算例的计算以及与其他文献的研究成果比较,证明该算法的优良性能。     

改进的遗传算法在作业调度中的应用

作业调度问题（JSP）是一类典型的NP-hard问题,遗传算法作为一种通用的优化算法在求解JSP中得到了广泛的应用。本文主要针对作业车间调度问题,基于改进的遗传算法 ,根据种群的进化状况,从而确定种群的适应度值,使之能够保持种群的多样化。     

分布式估计算法在考虑差异工件的并行批处理机调度中的应用

论文考虑包含差异工件的并行批处理机调度问题,优化目标是最小化制造跨度.在不违背机器容量的限制下,所有工件需要被分成不同的批次,然后被安排在机器上进行加工.首先根据问题提出一个混合整数规划模型,并提出一个下界;采用FF-LPT规则实现对工件的分批和排序;然后提出基于4种更新机制的分布式估计算法(EDA)来对问题求解.最后通过实验对各类规模不同的算例进行仿真,并将结果和模拟退火算法(SA)、遗传算法(GA)作对比,验证了算法的有效性.     

免疫克隆选择算法求解柔性生产调度问题

为减少计算复杂度,将具有解决复杂组合优化问题的免疫克隆选择算法应用于求解柔性生产调度问题.首先设计一种有效的抗原和抗体的数据结构,用抗原表示待调度的生产计划,抗体表示高效的柔性生产调度结果;然后着重设计了用于产生高效的柔性生产调度结果的克隆免疫算子;最后运用该模型对一个实际生产系统进行仿真调度决策,实验评估结果验证了算法的正确性和有效性.     

应用新型萤火虫算法求解Job-shop调度问题

Job shop调度问题是一类具有很高理论研究和工程应用价值的问题。针对该问题提出一种新型萤火虫求解算法;分析了萤火虫算法的仿生原理;给出了萤火虫算法求解JSP问题的求解步骤;并通过典型基准测试实例对算法进行了仿真实验;并与GA和PSO算法进行了比较;验证了该算法参数少;操作简单;收敛速度快;在生产调度中有广泛的应用前景。     

面向柔性生产资源的分布式农机生产调度优化

在经济全球化背景下,分布式制造和调度系统已成为大型农机生产企业的主流生产模式.针对农机生产过程中多品种小批量的生产特点,构建出一种分布式两阶段异构混合流水车间调度问题模型,提出了一种知识引导的分布估计算法,求解分布式异构混合流水车间调度问题模型的子问题:工厂分配、工件加工顺序和加工机器分配.改进的分布估计算法融合了多种启发式构造和随机方法进行种群初始化,并对候选解进行迭代优化,通过对求解问题的特性进行分析,提高关键加工阶段加工资源的利用率,对于不同规模的调度问题提出了相应的知识引导的强化机制和多种局部搜索策略.通过仿真实验,将提出的算法与其他三类算法进行对比,验证了改进的分布估计算法的有效性和稳定性.实验结果表明,利用调度问题特性引导算法的演化过程,可有效地提升知识引导的分布估计算法对于分布式异构混合流水车间调度问题的求解效率.     

多工艺路线车间作业调度遗传算法实现

针对简单遗传算法在解决作业车间调度问题时只适用于简单问题的局限,研究了多工艺路线的批量调度遗传算法实现,论述了3种提高生产效率的调度策略,即采用最小批量原则对零件进行分批调度生产;将批量准备时间和零件加工时间相分离,在工件到达加工机床前做好批量加工准备;在生产加工过程中,将同批加工零件进行多次机床间转移,缩短后续机床的等待时间.同时将工序优先级调度算法加入到简单遗传算法,提出了一种全局优化的多工艺路线批量生产调度混合遗传算法.仿真结果表明,该调度算法能取得较好的效果.     

Flexible job-shop scheduling with parallel variable neighborhood search algorithm

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. FJSP is NP-hard and mainly presents two difficulties. The first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on the machines. This paper proposes a parallel variable neighborhood search (PVNS) algorithm that solves the FJSP to minimize makespan time. Parallelization in this algorithm is based on the application of multiple independent searches increasing the exploration in the search space. The proposed PVNS uses various neighborhood structures which carry the responsibility of making changes in assignment and sequencing of operations for generating neighboring solutions. The results obtained from the computational study have shown that the proposed algorithm is a viable and effective approach for the FJSP.     

An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very difficult to solve multi-objective FJSP very well. In this paper, a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSP with several conflicting and incommensurable objectives. PSO which integrates local search and global search scheme possesses high search efficiency. And, TS is a meta-heuristic which is designed for finding a near optimal solution of combinatorial optimization problems. Through reasonably hybridizing the two optimization algorithms, an effective hybrid approach for the multi-objective FJSP has been proposed. The computational results have proved that the proposed hybrid algorithm is an efficient and effective approach to solve the multi-objective FJSP, especially for the problems on a large scale.     

柔性作业车间人员配置及作业排序问题研究*

以最小化任务完成时间为目标,建立了柔性作业车间人员配置及作业排序模型,并设计了蚁群-遗传混合优化算法进行求解。首先,根据求解问题特征,设计了蚁群-遗传协调优化的算法结构。其中,蚁群算法求解资源配置,遗传算法求解既定资源配置方案下的作业排序;其次,为便于蚂蚁游历中配置任务的加工设备和操作人员,设计了一种新的蚂蚁游历地图及地图上启发式信息的计算方法和更新方式;再次,遗传算法采用基于工序优先权值的实数编码方式,并采用父子排序的精英保留策略以促进算法收敛;最后,通过两个不同规模的实例,比较其与其他算法及不同资源配置规则的运行结果,说明本算法能较好的求解柔性作业车间的人员配置及作业排序问题。