基于新型帝国竞争算法的高维多目标柔性作业车间调度

针对高维多目标柔性作业车间调度问题(MaOFJSP),提出了一种新型帝国竞争算法(ICA)以同时最小化最大完成时间、最大拖期、最大机器负荷和总能耗,该算法采用新方法构建初始帝国使得大多数殖民国家分配数量相近的殖民地,引入殖民国家的同化,并应用新的革命策略和帝国竞争方法以获得高质量解.最后通过大量实验测试ICA新策略对其性能的影响并将ICA与其他算法对比,实验结果表明新型ICA在求解MaOFJSP方面具有较强的优势.     

A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling

Finding feasible scheduling that optimize all objective functions for flexible job shop scheduling problem (FJSP) is considered by many researchers. In this paper, the novel hybrid genetic algorithm and simulated annealing (NHGASA) is introduced to solve FJSP. The NHGASA is a combination of genetic algorithm and simulated annealing to propose the algorithm that is more efficient than others. The three objective functions in this paper are: minimize the maximum completion time of all the operations (makespan), minimize the workload of the most loaded machine and minimize the total workload of all machines. Pareto optimal solution approach is used in NHGASA for solving FJSP. Contrary to the other methods that assign weights to all objective functions to reduce them to one objective function, in the NHGASA and during all steps, problems are solved by three objectives. Experimental results prove that the NHGASA that uses Pareto optimal solutions for solving multi-objective FJSP overcome previous methods for solving the same benchmarks in the shorter computational time and higher quality.     

考虑学习效应的单人作业车间调度算法

单人负责多台机器的单一工序作业车间场景中,工人由于重复操作机器而产生学习效应.针对考虑依赖工件位置学习效应的单人单工序作业车间最小化最大完工时间的调度问题,建立一种混合整数规划模型.为解决该问题,设计一个考虑学习效应的贪婪算子,利用该算子构造两种贪婪算法,并提出一种基于贪婪的模拟退火算法.为衡量混合整数规划模型、贪婪算法和基于贪婪的模拟退火算法的性能,设计两种规模问题的数据实验.通过实验得出:现代混合整数规划模型求解器可以解决机器数量和工件总数量乘积小于75的小规模问题;基于贪婪的模拟退火算法求解此问题具有有效性,适用于各种规模的问题;间隔插入贪婪算法解决此问题速度较快,效果良好,可以应用于需要快速求解的场景.     

Mathematical modeling and heuristic approaches to flexible job shop scheduling problems

Scheduling for the flexible job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem in medium and actual size problem with traditional optimization approaches owing to the high computational complexity. For solving the realistic case with more than two jobs, two types of approaches have been used: hierarchical approaches and integrated approaches. In hierarchical approaches assignment of operations to machines and the sequencing of operations on the resources or machines are treated separately, i.e., assignment and sequencing are considered independently, where in integrated approaches, assignment and sequencing are not differentiated. In this paper, a mathematical model and heuristic approaches for flexible job shop scheduling problems (FJSP) are considered. Mathematical model is used to achieve optimal solution for small size problems. Since FJSP is NP-hard problem, two heuristics approaches involve of integrated and hierarchical approaches are developed to solve the real size problems. Six different hybrid searching structures depending on used searching approach and heuristics are presented in this paper. Numerical experiments are used to evaluate the performance of the developed algorithms. It is concluded that, the hierarchical algorithms have better performance than integrated algorithms and the algorithm which use tabu search and simulated annealing heuristics for assignment and sequencing problems consecutively is more suitable than the other algorithms. Also the numerical experiments validate the quality of the proposed algorithms.     

基于改进帝国竞争算法的柔性作业车间机器故障重调度

针对机器故障下的柔性作业车间重调度问题,提出了一种改进的帝国竞争算法(ICA).首先,以最大完工时间、机器能耗和总延迟时间为目标函数建立柔性作业车间动态重调度模型,并对三个目标采用线性加权法;然后提出了改进的ICA来把优良的信息保留到下一代,即在传统ICA的同化和革命步骤后加入一个轮盘赌的选择机制,使初始帝国中的优秀基...     

Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop

Much of the research on operations scheduling problems has ignored dynamic events in real-world environments where there are complex constraints and a variety of unexpected disruptions. Besides, while most scheduling problems which have been discussed in the literature assume that machines are incessantly available, in most real life industries a machine can be unavailable for many reasons, such as unanticipated breakdowns (stochastic unavailability), or due to a scheduled preventive maintenance where the periods of unavailability are determined in advance (deterministic unavailability). This paper describes how we can integrate simulation into genetic algorithm to the dynamic scheduling of a flexible job shop with machines that suffer stochastic breakdowns. The objectives are the minimization of two criteria, expected makespan and expected mean tardiness. An overview of the flexible job shops and scheduling under the stochastic unavailability of machines are presented. Subsequently, the details of integrating simulation into genetic algorithm are described and implemented. Consequently, problems of various sizes are used to test the performance of the proposed algorithm. The results obtained reveal that the relative performance of the algorithm for both abovementioned objectives can be affected by changing the levels of the breakdown parameters.     

求解有限产能作业车间调度的改进蚂蚁算法

通过对有限产能车间调度问题的分析,提出了基于蚂蚁算法求解该问题的方法。在模型的构建中增加了成本和机器负荷约束。通过产品的BOM表采用蚂蚁算法搜寻节点,做各阶层工序安排,将各阶层工序安排组合成一完整解。对蚂蚁算法进行了改进,在基本蚂蚁算法的基础上,通过修改信息素局域更新规则和全局更新规则,引入自适应信息素挥发系数来提高算法的收敛速度和全局最优解搜索能力。算例分析表明,蚂蚁的正向反馈及探索功能对求解较大工件数的生产计划非常有效。而且在有限产能的环境中根据产能负荷状况产生不同的外包组合,将满足交货期的各种外包组合成本做敏感性分析,供决策者参考。     

柔性作业调度的串并行模型对比与求解

作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。     

A very fast TS/SA algorithm for the job shop scheduling problem

The job shop scheduling problem (JSP) is one of the most notoriously intractable NP-complete optimization problems. Over the last 10–15 years, tabu search (TS) has emerged as an effective algorithmic approach for the JSP. However, the quality of solutions found by tabu search approach depends on the initial solution. To overcome this problem and provide a robust and efficient methodology for the JSP, the heuristics search approach combining simulated annealing (SA) and TS strategy is developed. The main principle of this approach is that SA is used to find the elite solutions inside big valley (BV) so that TS can re-intensify search from the promising solutions. This hybrid algorithm is tested on the standard benchmark sets and compared with the other approaches. The computational results show that the proposed algorithm could obtain the high-quality solutions within reasonable computing times. For example, 17 new upper bounds among the unsolved problems are found in a short time.     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

FICA: fuzzy imperialist competitive algorithm

Despite the success of the imperialist competitive algorithm （ICA） in solving optimization problems, it still suffers from frequently falling into local minima and low convergence speed. In this paper, a fuzzy version of this algorithm is proposed to address these issues. In contrast to the standard version of ICA, in the proposed algorithm, powerful countries are chosen as imperialists in each step;according to a fuzzy membership function, other countries become colonies of all the empires. In ab-sorption policy, based on the fuzzy membership function, colonies move toward the resulting vector of all imperialists. In this algorithm, no empire will be eliminated;instead, during the execution of the algorithm, empires move toward one point. Other steps of the algorithm are similar to the standard ICA. In experiments, the proposed algorithm has been used to solve the real world optimization problems presented for IEEE-CEC 2011 evolutionary algorithm competition. Results of experiments confirm the performance of the algorithm.     

A model and imperialist competitive algorithm for hybrid flow shops with sublots and setup times

This paper considers the problem of hybrid flow shops with sublots and sequence dependent setup times to minimize the total tardiness. A mixed integer linear programming model is presented for the problem. The paper also proposes an imperialist competitive algorithm. This algorithm utilizes three effective features of imperialist behavior, imperialist competition and colony improving mechanisms. To evaluate the algorithm, it is compared with optimal solution of the model and adaptations of two available algorithms. The results show that the effectiveness of the proposed model and algorithm.     

A hybrid immune simulated annealing algorithm for the job shop scheduling problem

A hybrid simulated annealing algorithm based on a novel immune mechanism is proposed for the job shop scheduling problem with the objective of minimizing total weighted tardiness. The proposed immune procedure is built on the following fundamental idea: the bottleneck jobs existing in each scheduling instance generally constitute the key factors in the attempt to improve the quality of final schedules, and thus, the sequencing of these jobs needs more intensive optimization. To quantitatively describe the bottleneck job distribution, we design a fuzzy inference system for evaluating the bottleneck level (i.e. the criticality) of each job. By combining the immune procedure with a simulated annealing algorithm, we design a hybrid optimization algorithm which is subsequently tested on a number of job shop instances. Computational results for different-sized instances show that the proposed hybrid algorithm performs effectively and converges fast to satisfactory solutions.     

双资源生产车间调度问题的研究

将遗传算法(GA)和模拟退火算法(SA)相结合研究了双资源生产车间的调度优化问题,该混合算法将机床设备和工人合理地分配给加工任务,使评价性能指标获得最优。通过与国内外学者的算法进行比较,本算法获得的生产周期最短,机床利用率和工人利用率都较高,并且在某些情况下,平均流动时间也较短。因此可以证明本算法具有一定的优越性。     

A hybrid Jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths

As an extension of the classical job shop scheduling problem, flexible job shop scheduling problem (FJSP) is considered as a challenge in manufacturing systems for its complexity and flexibility. Meta-heuristic algorithms are shown effective in solving FJSP. However, the multiple critical paths issue, which has not been formally discussed in the existing literature, is discovered to be a primary obstacle for further optimization by meta-heuristics. In this paper, a hybrid Jaya algorithm integrated with Tabu search is proposed to solve FJSP for makespan minimization. Two Jaya operators are designed to improve solutions under a two-vector encoding scheme. During the local search phase, three approaches are proposed to deal with multiple critical paths and have been evaluated by experimental study and qualitative analyses. An incremental parameter setting strategy and a makespan estimation method are employed to speed up the searching process. The proposed algorithm is compared with several state-of-the-art algorithms on three well-known FJSP benchmark sets. Extensive experimental results suggest its superiority in both optimality and stability. Additionally, a real world scheduling problem, including six instances with different scales, is applied to further prove its ability in handling large-scale scheduling problems.     

柔性Job shop集成化计划调度模型及其求解算法

考虑不同加工工艺路径的成本因素，从集成化的角度研究了柔性Job shop计划和调度问题，针对问题的结构特点，建立了两层混合整数规划模型，提出门槛接受，遗传算法与启发式规则相结合的混合求解算法，综合考虑各层次决策问题进行求解，实例计算表明，该算法可迅速求得问题的近优解，表现出良好的求解性能。     

Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion

This study investigates the flexible job shop scheduling problem (FJSP) with new job insertion. FJSP with new job insertion includes two phases: initializing schedules and rescheduling after each new job insertion. Initializing schedules is the standard FJSP problem while rescheduling is an FJSP with different job start time and different machine start time. The time to do rescheduling is the same as the time of new job insertion. Four ensembles of heuristics are proposed for scheduling FJSP with new job insertion. The objectives are to minimize maximum completion time (makespan), to minimize the average of earliness and tardiness (E/T), to minimize maximum machine workload (Mworkload) and total machine workload (Tworkload). Extensive computational experiments are carried out on eight real instances from remanufacturing enterprise. The results and comparisons show the effectiveness of the proposed heuristics for solving FJSP with new job insertion.     

A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems

This paper addresses the flexible job shop scheduling problem (fJSP) with three objectives: min makespan, min maximal machine workload and min total workload. We developed a hybrid genetic algorithm (GA) for the problem. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. In order to strengthen the search ability, individuals of GA are first improved by a variable neighborhood descent (VND), which involves two local search procedures: local search of moving one operation and local search of moving two operations. Moving an operation is to delete the operation, find an assignable time interval for it, and allocate it in the assignable interval. We developed an efficient method to find assignable time intervals for the deleted operations based on the concept of earliest and latest event time. The local optima of moving one operation are further improved by moving two operations simultaneously. An extensive computational study on 181 benchmark problems shows the performance of our approach.     

Flexible job shop scheduling using hybrid differential evolution algorithms

This paper proposes hybrid differential evolution (HDE) algorithms for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize the makespan. Firstly, a novel conversion mechanism is developed to make the differential evolution (DE) algorithm that works on the continuous domain adaptive to explore the problem space of the discrete FJSP. Secondly, a local search algorithm based on the critical path is embedded in the DE framework to balance the exploration and exploitation by enhancing the local searching ability. In addition, in the local search phase, the speed-up method to find an acceptable schedule within the neighborhood structure is presented to improve the efficiency of whole algorithms. Extensive computational results and comparisons show that the proposed algorithms are very competitive with the state of the art, some new best known solutions for well known benchmark instances have even been found.     

Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem

The multi-objective flexible job shop scheduling problem is solved using a novel path-relinking algorithm based on the state-of-the-art Tabu search algorithm with back-jump tracking. A routing solution is identified by problem-specific neighborhood search, and is then further refined by the Tabu search algorithm with back-jump tracking for a sequencing decision. The resultant solution is used to maintain the medium-term memory where the best solutions are stored. A path-relinking heuristics is designed to generate diverse solutions in the most promising areas. An improved version of the algorithm is then developed by incorporating an effective dimension-oriented intensification search to find solutions that are located near extreme solutions. The proposed algorithms are tested on benchmark instances and its experimental performance is compared with that of algorithms in the literature. Comparison results show that the proposed algorithms are competitive in terms of its computation performance and solution quality.