A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times

This paper examines the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such problems are quite common in the semiconductor manufacturing industry. In particular, this paper pays special attention to the chipset production in the semiconductor Assembly and Test Manufacturing (ATM) factory and constructs a Mixed Integer Programming (MIP) model for the problem. The primal problem is decomposed into a lot-sizing subproblem and a set of single-machine scheduling subproblems by Lagrangian decomposition. A Lagrangian-based heuristic algorithm, which incorporates the simulated annealing algorithm aimed at searching for a better solution during the feasibility construction stage, is proposed. Computational experiments show that the proposed hybrid algorithm outperforms other heuristic algorithms and meets the practical requirement for the tested ATM factory.     

A novel hybrid algorithm for scheduling steel-making continuous casting production

In this paper, steel-making continuous casting (SCC) scheduling problem (SCCSP) is investigated. This problem is a specific case of hybrid flow shop scheduling problem accompanied by technological constraints of steel-making. Since classic optimization methods fail to obtain an optimal solution for this problem over a suitable time, a novel iterative algorithm is developed. The proposed algorithm, named HANO, is based on a combination of ant colony optimization (ACO) and non-linear optimization methods.     

A hybrid genetic algorithm for no-wait job shop scheduling problems

A no-wait job shop (NWJS) describes a situation where every job has its own processing sequence with the constraint that no waiting time is allowed between operations within any job. A NWJS problem with the objective of minimizing total completion time is a NP-hard problem and this paper proposes a hybrid genetic algorithm (HGA) to solve this complex problem. A genetic operation is defined by cutting out a section of genes from a chromosome and treated as a subproblem. This subproblem is then transformed into an asymmetric traveling salesman problem (ATSP) and solved with a heuristic algorithm. Subsequently, this section with new sequence is put back to replace the original section of chromosome. The incorporation of this problem-specific genetic operator is responsible for the hybrid adjective. By doing so, the course of the search of the proposed genetic algorithm is set to more profitable regions in the solution space. The experimental results show that this hybrid genetic algorithm can accelerate the convergence and improve solution quality as well.     

Total flow time minimization in no-wait job shop using a hybrid discrete group search optimizer

The no-wait job shop scheduling problem is a well-known NP-hard problem and it is typically decomposed into timetabling subproblem and sequencing subproblem. By adopting favorable features of the group search technique, a hybrid discrete group search optimizer is proposed for finding high quality schedules in the no-wait job shops with the total flow time criterion. In order to find more promising sequences, the producer operator is designed as a destruction and construction (DC) procedure and an insertion-based local search, the scrounger operator is implemented by differential evolution scheme, and the ranger operator is designed by hybridizing best insert moves. An efficient initialization scheme based on Nawaz–Enscore–Ham (NEH) heuristic is designed to construct the initial population with both quality and diversity. A speed-up method is developed to accelerate the evaluation of the insertion neighborhood. Computational results based on well-known benchmark instances show that the proposed algorithm clearly outperforms a hybrid differential evolution algorithm and an iterated greedy algorithm. In addition, the proposed algorithm is comparable to a local search method based on optimal job insertion, especially for large-size instances.     

Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling

The expanded job-shop scheduling problem (EJSSP) is a practical production scheduling problem with processing constraints that are more restrictive and a scheduling objective that is more general than those of the standard job-shop scheduling problem (JSSP). A hybrid approach involving neural networks and genetic algorithm (GA) is presented to solve the problem in this paper. The GA is used for optimization of sequence and a neural network (NN) is used for optimization of operation start times with a fixed sequence.

After detailed analysis of an expanded job shop, new types of neurons are defined to construct a constraint neural network (CNN). The neurons can represent processing restrictions and resolve constraint conflicts. CNN with a gradient search algorithm, gradient CNN in short, is applied to the optimization of operation start times with a fixed processing sequence. It is shown that CNN is a general framework representing scheduling problems and gradient CNN can work in parallel for optimization of operation start times of the expanded job shop.

Combining gradient CNN with a GA for sequence optimization, a hybrid approach is put forward. The approach has been tested by a large number of simulation cases and practical applications. It has been shown that the hybrid approach is powerful for complex EJSSP.     

求解阻塞混合流水车间调度的双层变异迭代贪婪算法

混合流水车间调度是制造业领域的前沿方向,而研究带有阻塞约束的问题更具有现实意义.针对阻塞混合流水车间调度问题(BHFSP),以最小化最大完工时间为优化目标建立BHFSP的数学模型并详细阐述其计算过程,在零缓冲区特性的基础上设计一种双层变异策略的迭代贪婪(IGDLM)算法求解BHFSP.分析传统迭代贪婪(IG)算法中的优势和不足,针对阻塞特性提出双层变异策略来提高解的多样性,进一步平衡所提算法的全局探索和局部搜索能力.通过100个测试算例的数值仿真以及与5种代表算法的统计比较,验证所提出的双层变异策略与IG融合的算法能够得到更好的目标值,并为中大规模的BHFSP提供更优的调度方案.     

工序间存在零等待约束的复杂产品调度研究

针对实际装配生产中工序之间存在零等待约束的复杂产品的调度问题, 提出了一种把存在零等待约束的工序虚拟成一个工序的方法. 该方法在提出复杂产品、标准工序、虚拟工序、零等待和扩展加工工艺树的概念基础上, 对扩展加工工艺树中的标准工序采用拟关键路径法和最佳适应调度的车间调度算法进行调度, 对虚拟工序采用移动交换算法在相应设备上分离调度, 将存在零等待约束的调度问题转化为存在虚拟工序的无零等待约束的调度问题. 实例表明, 所提出的调度算法能够较好地解决具有实际意义的工序间存在零等待约束的复杂产品的调度问题, 且易于实现.     

Two‐stage hybrid flow shop with recirculation

In this paper, we present two scheduling hybrid flow shop problems to minimize the makespan. In each problem, we have two stages. In the first problem, one machine at each stage is considered with recirculation of jobs in the second stage (machine). We prove that this first problem is polynomial and we present an algorithm for its resolution. The second problem consists of one machine in the first stage and two identical parallel machines in the second. Jobs can be recirculated a fixed number of times in the second stage. We show that the problem is NP‐hard and a polynomial subproblem is proposed. Linear program and heuristics are also presented with numerical experimentations.     

求解并行机拖期与能耗成本优化调度的混合教一学算法

针对加工时间可控的并行机调度,提出了一类考虑拖期与能耗成本优化的调度问题。首先对调度问题进行了问题描述,并建立了整数线性规划模型以便于CPLEX求解。为了快速获得问题的满意解,提出了一种混合教-学算法。结合问题的性质,设计了编码与解码方法以克服标准教-学算法无法直接适用于离散问题的缺点。同时,构建了基于变邻域搜索的局部搜索算子以强化混合算法的搜索性能。最后,对加工时间可控的并行机调度问题进行了仿真实验,测试结果验证了本文构建的整数线性规划模型和混合算法的可行性和有效性。     

An effective heuristic method for generalized job shop scheduling with due dates

This paper is concerned with the generalized job shop scheduling problem with due dates wherein the objective is to minimize total job tardiness. An efficient heuristic algorithm called the revised exchange heuristic algorithm (REHA) is presented for solving this problem. It has been shown that the algorithm can be completed in polynomial time. Results, generated over a range of shop sizes with different due date tightness levels, indicate that the proposed technique is capable of yielding notable reductions in total tardiness (over initial schedules) for practical size problems. This suggests that this approach is an efficient scheduling option for this class of complex optimization problems.     

Scheduling of a single crane in batch annealing process

This paper studies a single crane scheduling problem motivated by batch annealing process in the iron and steel industry. Each coil stack placed on fixed base needs to go through two-stage processing: heating and cooling. During each stage, limited special machines (furnace and cooler) must be operated by crane, respectively. Our problem is to assign the shared machines and schedule a single crane for minimizing the last coil stack completion time (makespan). A mixed integer linear programming (MILP) model is formulated by considering both machine and crane positions. We show that the problem is NP-hard in the strong sense. Some optimal properties on the problem are derived. A two-phase algorithm is constructed for the problem. In the first phase, a fully polynomial time approximation scheme (FPTAS) is developed for the assignment subproblem. In the second phase, a heuristics is proposed for the scheduling subproblem. From an absolute performance point of view, we analyze the quality of the two-phase algorithm. We also consider special cases where some properties or algorithms are developed. In order to further verify the performance of the two-phase algorithm, we develop a lower bound on the optimal objective function. Computational experiments on the randomly generated problem instances show that the algorithm is close to the lower bound within a reasonable computation time.     

基于GSPN和人工免疫算法的并行测试任务调度研究

针对ATS中并行测试任务调度复杂、难以优化的问题,提出了一种广义随机Petri网和人工免疫算法相结合的任务调度优化算法.首先对并行测试系统建立广义随机Petri网(GSPN)模型,然后将激发的变迁序列集作为并行测试任务调度路径;将免疫克隆选择算法(ICSA)应用到并行测试系统任务调度问题中,并提出一种自适应克隆选择算子,搜索最优任务调度路径,得到以测试时间最短为目标的最优任务调度方案.用某型雷达接收机并行测试系统对该算法进行仿真验证,结果表明,与改进的混合遗传算法(IHGA)相比,该算法能够便捷地得到任务调度最优序列,且测试效率更高.     

改进粒子群算法求解应急项目瓶颈资源动态调度问题

应急项目中资源的调度受到多种随机因素影响,处于复杂动态的环境中,求解困难;约束理论指出瓶颈是复杂系统管理的核心,将调度的重点放在瓶颈资源上可以简化复杂系统问题。针对于此,研究了应急项目中瓶颈资源的动态调度问题,以达到提高资源的利用率、减轻损失等目的。首先,从优化目标、机器环境、作业特征和约束几方面分析并描述了应急项目中瓶颈资源调度的问题特征,建立了相应的数学模型;接着,运用混合重调度策略和改进粒子群算法进行算法设计,实现了瓶颈资源的动态调度;最后,通过仿真实验并对比了多种算法的结果,验证了该算法的可行性和有效性,证明其具有较好的理论和实际应用价值。     

微电子生产过程调度问题基于指标快速预报的分解算法

微电子生产过程调度问题具有规模大和约束复杂等特点,如菜单、Setup时间和组批约束等,其优化调度具有一定难度.针对以最小化平均流经时间为调度目标的较大规模微电子生产过程调度问题,提出一种基于指标快速预报的分解方法(DM-IFP).首先,通过松弛不可中断约束,设计一种代理方法,即基于机器负载的操作完工时间快速预测方法(CTP-ML);其次,设计基于CTP-ML的问题分解方法,将原问题迭代分解为多个连续交迭的子问题;然后,提出一种基于双信息素的蚁群算法(ACO-D)用于求解分解后的子问题,其全局调度目标采用CTP-ML获取,有效保证了全局优化性能;最后,针对一些不同规模的仿真数据,将所提出方法与一些代表性的算法进行详尽的数值对比,计算结果表明所提出方法在所获解的质量和收敛性上均有改善.     

A hybrid approach to large-scale job shop scheduling

A decomposition based hybrid optimization algorithm is presented for large-scale job shop scheduling problems in which the total weighted tardiness must be minimized. In each iteration, a new subproblem is first defined by a simulated annealing approach and then solved using a genetic algorithm. We construct a fuzzy inference system to calculate the jobs’ bottleneck characteristic values which depict the characteristic information in different optimization stages. This information is then utilized to guide the process of subproblem-solving in an immune mechanism in order to promote the optimization efficiency. Numerical computational results show that the proposed algorithm is effective for solving large-scale scheduling problems.     

A hybrid meta-heuristic algorithm for optimization of crew scheduling

Crew scheduling problem is the problem of assigning crew members to the flights so that total cost is minimized while regulatory and legal restrictions are satisfied. The crew scheduling is an NP-hard constrained combinatorial optimization problem and hence, it cannot be exactly solved in a reasonable computational time. This paper presents a particle swarm optimization (PSO) algorithm synchronized with a local search heuristic for solving the crew scheduling problem. Recent studies use genetic algorithm (GA) or ant colony optimization (ACO) to solve large scale crew scheduling problems. Furthermore, two other hybrid algorithms based on GA and ACO algorithms have been developed to solve the problem. Computational results show the effectiveness and superiority of the proposed hybrid PSO algorithm over other algorithms.     

求解混合流水车间调度问题的一种遗传算法

由于高度的计算复杂性(NP-hard问题),混合流水车间调度问题很难求得最优解,启发式算法和智能优化算法(如遗传算法)求解此类问题的近优解的有效性和实用性已被证实。该文提出了一种基于遗传算法的求解方法,在由染色体转换成可行调度的过程中引入工件插入方法,同时设计了一种新的交叉算子。通过大量的数值计算表明,该算法的优化质量大大优于传统的遗传算法和NEH启发式算法。     

Optimizing the stretch of independent tasks on a cluster: From sequential tasks to moldable tasks

This paper addresses the problem of scheduling non-preemptive moldable tasks to minimize the stretch of the tasks in an online non-clairvoyant setting. To the best of the authors’ knowledge, this problem has never been studied before. To tackle this problem, first the sequential subproblem is studied through the lens of the approximation theory. An algorithm, called DASEDF, is proposed and, through simulations, it is shown to outperform the first-come, first-served scheme. Furthermore, it is observed that machine availability is the key to getting good stretch values. Then, the moldable task scheduling problem is considered, and, by leveraging the results from the sequential case, another algorithm, DBOS, is proposed to optimize the stretch while scheduling moldable tasks. This work is motivated by a task scheduling problem in the context of parallel short sequence mapping which has important applications in biology and genetics. The proposed DBOS algorithm is evaluated both on synthetic data sets that represent short sequence mapping requests and on data sets generated using log files of real production clusters. The results show that the DBOS algorithm significantly outperforms the two state-of-the-art task scheduling algorithms on stretch optimization.     

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.     

基于混合人工蜂群算法的并行测试任务优化研究

并行测试技术可以同时进行多个任务的测试,提高资源利用率,节约测试成本;并行测试调度问题是一种复杂的组合优化问题,是并行测试技术的核心要素;并行测试系统作为并行测试技术的载体,自身的性能和求解效率尤其重要;对并行测试完成时间极限定理进行了研究,建立了并行测试任务调度的数学模型,分析了传统元启发式算法求解并行测试问题的不足,提出了基于动态规划的递归搜索技术和人工蜂群算法相结合的混合人工蜂群算法,并采用整数规划精确算法和遗传算法对混合人工蜂群算法进行验证;得出结论采用混合人工蜂群算法进行并行测试任务的调度节约了接近50%的时间,降低了约20%的硬件资源占用,提高了测试效率,可以满足工程实际的应用。