A new optimization approach for nozzle selection and component allocation in multi-head beam-type SMD placement machines

This paper addresses a highly challenging scheduling problem faced in multi-head beam-type surface mounting devices (SMD) machines. An integrated mathematical model is formulated aiming to balance workloads over multiple heads as well as improving the traveling speed of the robotic arm by incorporating the appropriateness factors in the model to evaluate the compatibility of component-nozzle pairs. The proposed model is a bi-objective mixed integer nonlinear programming one, which is first converted into a linearized model and then directly solved by using the augmented epsilon constraint method for small problem instances. As the model is turned out to be NP-hard, we also develop a Multi-Objective Particle Swarm Optimization (MOPSO) algorithm to solve the model for medium and large-sized problem instances. The parameters of the proposed MOPSO are tuned by using the Taguchi Method and corresponding numerical results are provided.     

Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound

We propose exact hybrid methods based on integer linear programming (ILP) and constraint programming (CP) for an integrated employee timetabling and job-shop scheduling problem. Each method we investigate uses a CP formulation associated with an LP relaxation. Under a CP framework, the LP relaxation is integrated into a global constraint using in addition reduced cost-based filtering techniques. We propose two CP formulations of the problem yielding two different LP relaxations. The first formulation is based on a direct representation of the problem. The second formulation is based on a decomposition in intervals of the possible operation starting times. We show the theoretical interest of the decomposition-based representation compared to the direct representation through the analysis of dominant schedules. Computational experiments on a set of randomly generated instances confirm the superiority of the decomposition-based representation. In both cases, the hybrid methods outperform pure CP for employee cost minimization while it is not the case for makespan minimization. The experiments also investigate the interest of the proposed integrated method compared to a sequential approach and show its potential for multiobjective optimization.     

生物地理学算法求解柔性车间作业调度问题

针对加工设备和操作工人双资源约束的柔性作业车间调度问题,建立以生产时间和生产成本为目标函数的柔性作业车间调度模型,提出基于模糊Pareto支配的生物地理学算法,采用模糊Pareto支配的方法计算解之间的支配关系并对Pareto解集排序,进行全局最优值的更新,并采用余弦迁移模型来改善生物地理学算法的收敛速度。将该方法应用于某模具车间的柔性作业车间调度中,仿真结果验证了该方法的可行性和有效性。     

A genetic algorithm for job-shop scheduling with operators enhanced by weak Lamarckian evolution and search space narrowing

The job-shop scheduling problem with operators is a very interesting problem that generalizes the classic job-shop problem in such a way that an operation must be algorithm to solve this problem considering makespan minimization. The genetic algorithm uses permutations with repetition to encode chromosomes and a schedule generation scheme, termed OG&T, as decoding algorithm. This combination guaranties that at least one of the chromosomes represents and optimal schedule and, at the samhat machines and operators are idle while an operation is available to be processed. To improve the quality of the schedules for large instances, we use Lamarckian evolution and modify the OG&T algorithm to further reduce the idle time of the machines and operators, in this case at the risk of leaving all optimal schedules out of the search space. We conducted a large experimental study showing that these improvements allow the genetic algorithm to reach high quality solutions in very short time, and so it is quite competitive with the current state-of-the-art methods.     

A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem

This paper deals with a bi-objective flowshop scheduling problem minimizing the makespan and total weighted tardiness, in which all jobs may not be processed by all machines. Furthermore, we consider transportation times between machines. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. This paper presents a new multi-objective electromagnetism algorithm (MOEM). The motivation behind this algorithm has risen from the attraction–repulsion mechanism of electromagnetic theories. Along with MOEA, we apply simulated annealing to solve the given problem. A set of experimental instances are carried out to evaluate the algorithm by advanced multi-objective performance measures. The related results show that a variant of our proposed MOEM provides sound performance comparing with other algorithms.     

求解作业车间调度问题的改进混合灰狼优化算法*

灰狼优化算法(GWO)是目前一种比较新颖的群智能优化算法,具有收敛速度快,寻优能力强等优点。本文将灰狼优化算法用于求解复杂的作业车间调度问题,与布谷鸟搜索算法进行比较研究,验证了标准GWO算法求解经典作业车间调度问题的可行性和有效性。在此基础上,针对复杂作业车间调度问题难以求解的特点,对标准GWO算法进行改进,通过进化种群动态、反向学习初始化种群,以及最优个体变异等三个方面的改进操作,测试结果表明改进后的混合灰狼优化算法能够有效跳出局部最优值,找到更好的解,并且结果鲁棒性更强。     

A three-fold approach for job shop problems: A divide-and-integrate strategy with immune algorithm

This paper presents a novel divide-and-integrate strategy based approach for solving large scale job-shop scheduling problems. The proposed approach works in three phases. First, in contrast to traditional job-shop scheduling approaches where optimization algorithms are used directly regardless of problem size, priority rules are deployed to decrease problem scale. These priority rules are developed with slack due dates and mean processing time of jobs. Thereafter, immune algorithm is applied to solve each small individual scheduling module. In last phase, integration scheme is employed to amalgamate the small modules to get gross schedule with minimum makespan. This integration is carried out in dynamic fashion by continuously checking the preceding module's machine ideal time and feasible slots (satisfying all the constraint). In this way, the proposed approach will increase the machine utilization and decrease the makespan of gross schedule. Efficacy of the proposed approach has been tested with extremely hard standard test instances of job-shop scheduling problems. Implementation results clearly show effectiveness of the proposed approach.     

Two-machine flow shop scheduling problem with blocking,multi-task flexibility of the first machine,and preemption

Blocking flow shop scheduling problem has been extensively studied in recent years; however, some applications mentioned for this problem have some additional characteristics that have not been well considered. Multi-task flexibility of machines and preemption are two of such characteristics. Multi-task flexible machines are capable of processing the operations of at least one other machine in the system. In addition, if preemption is allowed, the solution space grows, and solutions that are more efficient may be obtained. In this study, the two-machine flow shop scheduling problem with blocking, multi-task flexibility of the first machine, and preemption is investigated by considering the minimization of makespan as criterion. It is proved that the complexity of the problem is strongly NP-hard. Because of preemption and multi-task flexibility, there are infinite schedules for each sequence; however, it is shown that a dominant schedule can be defined for each sequence. Two mathematical models are proposed for optimally solving the small-sized instances. Furthermore, a variable neighborhood search algorithm (VNS) and a new variant of it, namely, dynamic VNS (DVNS), are presented to find high quality solutions for large-sized instances. Unlike the VNS algorithm, the DVNS algorithm does not need tuning for the shaking phase. Nevertheless, computational results show that DVNS has even a slightly better performance. The VNS and DVNS algorithms are also compared with some of the best-performing metaheuristics already developed for the flow shop scheduling problem with blocking and minimization of makespan as criterion. Computational results reveal that both algorithms are superior to the others for large-sized instances.     

带机器人制造单元的作业车间调度仿真

针对带有机器人制造单元的作业车间调度优化问题, 在若干加工机器上可以加工具有特定加工工序的若干工件, 并且搬运机器人可以将工件在装卸载站与各加工机器间进行搬运. 在实际生产过程中, 由于不确定性, 特别是带有存货的加工单元, 要求工件的完工时间在一个时间窗内, 而不是一个特定的时间点. 因此针对此情况的作业车间, 考虑到其在求解问题过程中的复杂性和约束性等特点, 研究了在时间窗约束下, 目标值为最小化工件完成时间提前量和延迟量的总权重. 提出了一种将文化基因算法与邻域搜索技术(变邻域下降搜索)相结合的改进元启发式算法, 在求得最优目标值的同时, 可得到最优值的工件加工序列及机器人搬运序列. 通过实验结果表明, 所提出的算法有效且优于传统文化基因算法与遗传算法.     

基于蚁群粒子群算法求解多目标柔性调度问题

通过分析多目标柔性作业车间调度问题中各目标的相互关系,提出一种主、从递阶结构的蚁群粒子群求解算法。算法中,主级为蚁群算法,在选择工件加工路径过程中实现设备总负荷和关键设备负荷最小化的目标;从级为粒子群算法,在主级工艺路径约束下的设备排产中实现工件流通时间最小化的目标。然后,以设备负荷和工序加工时间为启发式信息设计蚂蚁在工序可用设备间转移概率;基于粒子向量优先权值的大小关系设计解码方法实现设备上的工序排产。最后,通过仿真和比较实验,验证了该算法的有效性。     

精英进化策略求解柔性作业车间调度问题

柔性作业车间调度问题允许一道工序可以在多个可选机器上进行加工,减少了机器约束,增加了求解难度,是典型的NP难问题。结合其特点,设计了一种精英进化策略遗传算法求解柔性作业车间调度问题。提出了解阀值的指标,使得外部精英库中不仅保留算法每次迭代过程中的最优解,而且保留最优值相等而调度方案不同的解,为调度人员提供更多选择。通过制造企业中的实际案例和其它文献中的案例对提出的精英进化策略遗传算法进行了测试,结果证明提出方法的有效性。     

改进蝙蝠算法柔性作业车间调度问题研究

针对柔性作业车间调度问题,提出了一种改进的离散蝙蝠算法。该算法采用双层编码序列方式,利用均衡机器负载分配策略和插入式解码方案初始化种群,同时设计了离散蝙蝠算法的速度、位置更新的相关算子和操作,引入了平衡调整因子改善算法搜索能力。通过案例测试并与其他算法比较,验证了改进的离散蝙蝠算法可以有效地求解柔性作业车间调度问题,并具有较高的精确度。     

Modeling and scheduling a case of flexible flowshops: Total weighted tardiness minimization

Two of the most realistic assumptions in the field of scheduling are the consideration of setup and transportation times. In this paper, we study the flexible flowshop scheduling where setup times are anticipatory sequence-dependent and transportation times are job-independent. We also assume that there are several transporters to carry jobs. The objective is to minimize total weighted tardiness. We first formulate the problem as a mixed integer linear programming (MILP) model. With this, we solve small-sized instances to optimality. Since this problem is known to be NP-hard, we then propose an effective metaheuristic to tackle large-sized instances. This metaheuristic, called electromagnetism algorithm (EMA), originates from the attraction–repulsion mechanism of the electromagnetism theory. We conduct a series of experiments and complete statistical analyses to evaluate the performance of the proposed MILP model and EMA. On a set of instances, we first tune the parameters of EMA. Then, the efficiency of the model and general performance of the proposed EMA are assessed over a set of small-sized instances. To further evaluate EMA, we compare it against two high performing metaheuristics existing in the literature over a set of large-sized instances. The results demonstrate that the proposed MILP model and EMA are effective for this problem.     

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

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

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.     

强化学习和仿真相结合的车间作业排序系统

设计了一个强化学习和仿真相结合的动态实时车间作业排序系统．首先引入多个随机变量，将车间作业排序问题转换成序贯决策问题；然后通过仿真手段构建车间作业排序问题的模型环境，求取系统性能指标并保证解的可行性；接着设计了一个多智能体Q学习算法和仿真集成解决作业排序问题；最后通过仿真优化实验验证了该系统的有效性．     

Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms

In contrast to traditional job-shop scheduling problems, various complex constraints must be considered in distributed manufacturing environments; therefore, developing a novel scheduling solution is necessary. This paper proposes a hybrid genetic algorithm (HGA) for solving the distributed and flexible job-shop scheduling problem (DFJSP). Compared with previous studies on HGAs, the HGA approach proposed in this study uses the Taguchi method to optimize the parameters of a genetic algorithm (GA). Furthermore, a novel encoding mechanism is proposed to solve invalid job assignments, where a GA is employed to solve complex flexible job-shop scheduling problems (FJSPs). In addition, various crossover and mutation operators are adopted for increasing the probability of finding the optimal solution and diversity of chromosomes and for refining a makespan solution. To evaluate the performance of the proposed approach, three classic DFJSP benchmarks and three virtual DFJSPs were adapted from classical FJSP benchmarks. The experimental results indicate that the proposed approach is considerably robust, outperforming previous algorithms after 50 runs.     

Course timetabling using evolutionary operators

Timetabling is the problem of scheduling a set of events while satisfying various constraints. In this paper, we develop and study the performance of an evolutionary algorithm, designed to solve a specific variant of the timetabling problem. Our aim here is twofold: to develop a competitive algorithm, but more importantly, to investigate the applicability of evolutionary operators to timetabling. To this end, the introduced algorithm is tested using a benchmark set. Comparison with other algorithms shows that it achieves better results in some, but not all instances, signifying strong and weak points. To further the study, more comprehensive tests are performed in connection with another evolutionary algorithm that uses strictly group-based operators. Our analysis of the empirical results leads us to question single-level selection, proposing, in its place, a multi-level alternative.     

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.     

A fast estimation of distribution algorithm for dynamic fuzzy flexible job-shop scheduling problem

Due to the complicated circumstances in workshop, most of the conventional scheduling algorithms fail to meet the requirements of instantaneity, complexity, and dynamicity in job-shop scheduling problems. Compared with the static algorithms, dynamic scheduling algorithms can better fulfill the requirements in real situations. Considering that both flexibility and fuzzy processing time are common in reality, this paper focuses on the dynamic flexible job-shop scheduling problem with fuzzy processing time (DfFJSP). By adopting a series of transforming procedures, the original DfFJSP is simplified as a traditional static fuzzy flexible job-shop problem, which is more suitable to take advantage of the existing algorithms. In this paper, estimation of distribution algorithm (EDA) is brought into address the post-transforming problem. An improved EDA is developed through making use of several elements omitted in original EDA, including the historical-optimal solution and the standardized solution vectors. The improved algorithm is named as fast estimation of distribution algorithm (fEDA) since it performs better in convergence speed and computation precision, compared with the original EDA. To sum up, the ingenious transformation and the effective fEDA algorithm provide an efficient and practical way to tackle the dynamic flexible fuzzy job-shop scheduling problem.