RECONFIGURABLE PRODUCTION LINE MODELING AND SCHEDULING USING PETRI NETS AND GENETIC ALGORITHM

In response to the production capacity and functionality variations, a genetic algorithm (GA) embedded with deterministic timed Petri nets(DTPN) for reconfigurable production line(RPL) is proposed to solve its scheduling problem. The basic DTPN modules are presented to model the corresponding variable structures in RPL, and then the scheduling model of the whole RPL is constructed. And in the scheduling algorithm, firing sequences of the Petri nets model are used as chromosomes, thus the selection, crossover, and mutation operator do not deal with the elements in the problem space, but the elements of Petri nets model. Accordingly, all the algorithms for GA operations embedded with Petri nets model are proposed. Moreover, the new weighted single-objective optimization based on reconfiguration cost and E/T is used. The results of a DC motor RPL scheduling suggest that the presented DTPN-GA scheduling algorithm has a significant impact on RPL scheduling, and provide obvious improvements over the conventional scheduling method in practice that meets duedate, minimizes reconfiguration cost, and enhances cost effectivity.     

NEW NONSTANDARD JOB SHOP SCHEDULING ALGORITHM

Considering the complex constraint between operations in nonstandard job shop scheduling problem （NJSSP）, critical path of job manufacturing tree is determined according to priority scheduling function constructed. Operations are divided into dependent operations and independent operations with the idea of subsection, and corresponding scheduling strategy is put forward according to operation characteristic in the segment and the complementarities of identical function machines. Forward greedy rule is adopted mainly for dependent operations to make operations arranged in the right position of machine selected, then each operation can be processed as early as possible, and the total processing time of job can be shortened as much as possible. For independent operations optimum scheduling rule is adopted mainly, the inserting position of operations will be determined according to the gap that the processing time of operations is subtracted from idle time of machine, and the operation will be inserted in the position with minimal gap. Experiments show, under the same conditions, the result that operations are scheduled according to the object function constructed, and the scheduling strategy adopted is better than the result that operations are scheduled according to efficiency scheduling algorithm.     

DEADLOCK-FREE SCHEDULING METHOD BASED ON PETRI NET AND GA

An efficient algorithm for finding an optimal deadlock-free schedule in a manufacturingsystem with very limited buffer is presented. This algorithm is based on the effective genetic algorithm(GA) search method, and a formal Petri net structure is introduced to detect the token player assuringdeadlock-free. In order to make the scheduling strategy generated by GA meet the required constraintof deadlock-free, Petri net is involved to make the implementation of the job scheduling in an FMSdeadlock-free. The effectiveness and efficiency of the proposed approach is illustrated by using anexample.     

CAPACITATED LOT SIZING AND SCHEDULING PROBLEMS USING HYBRID GA／TS APPROACHES

The capacitated lot sizing and scheduling probbm that involves in determining the production amounts and release dates for several items over a given planning horizon are given to meet dynamic order demand without incurring backloggings. Thi: problem considering overtime capacity is studied. The mathematical model is presented, and a genelic algorithm (GA) approach is developed to solve the problem. The initial solutions are generated after using heuristic method. Capacity balancing procedure is employed to stipulate the feasibility of the solutions. In addition, a technique based on Tabu search (TS) is inserted into the genetic algorithm to d;al with the scheduled overtime and help the convergence of algorithm. Computational simulation is conducted to test the efficiency of the proposed hybrid approach, which turns out to improve both the solution quality and execution speed.     

APPLYING PARTICLE SWARM OPTIMIZATION TO JOB-SHOPSCHEDULING PROBLEM

A new heuristic algorithm is proposed for the problem of finding the minimum makespan in the job-shop scheduling problem. The new algorithm is based on the principles of particle swarm optimization (PSO). PSO employs a collaborative population-based search, which is inspired by the social behavior of bird flocking. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Simulated annealing (SA) employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule. By reasonably combining these two different search algorithms, a general, fast and easily implemented hybrid optimization algorithm, named HPSO, is developed. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated by applying it to some benchmark job-shop scheduling problems and comparing results with other algorithms in literature. Comparing results indicate that PSO-based a     

Parallel Test Tasks Scheduling and Resources Configuration Based on GA-ACA

A Genetic Algorithm-Ant Colony Algorithm(GA-ACA),which can be used to optimize multi-Unit Under Test(UUT)parallel test tasks sequences and resources configuration quickly and accurately,is proposed in the paper.With the establishment of the mathematic model of multi-UUT parallel test tasks and resources,the condition of multi-UUT resources mergence is analyzed to obtain minimum resource requirement under minimum test time.The definition of cost efficiency is put forward,followed by the design of gene coding and path selection project,which can satisfy multi-UUT parallel test tasks scheduling.At the threshold of the algorithm,GA is adopted to provide initial pheromone for ACA,and then dual-convergence pheromone feedback mode is applied in ACA to avoid local optimization and parameters dependence.The practical application proves that the algorithm has a remarkable effect on solving the problems of multi-UUT parallel test tasks scheduling and resources configuration.     

Rule- and PSO algorithm-based dynamic spatial rescheduling method for hull curved block construction

Due to no effective rescheduling method in hull curved block construction planning, existing scheduling planning can’t be applied in practical production effectively. Two-dimensional layout and dynamic attributes of block construction planning are considered to develop a spatial rescheduling method, which is based on the spatial points searching rule and the particle swarm optimization(PSO) algorithm. A dynamic spatial rescheduling method is proposed to solve the manufacturing problem of rush-order blocks. Through spatial rescheduling, the rescheduling start time, the current processing information set and rescheduling blocks set can be obtained automatically. By using and updating the data of these sets, the rescheduling method combines the PSO algorithm with the spatial points searching rule to determine the rescheduling start time and layout of the blocks. Three types of dynamic events, including rush-order block delay, existing block delay and existing block position changes, are used to address problems with different function goals by setting different function weights. Finally, simulations based on three types of rush-order block events are performed to validate this method, including single rush-order block, multi rush-order blocks at the same time and multi rush-order blocks at different times. The simulation results demonstrate that this method can solve the rush-order block problems in hull block construction and reduce the interference to the existing manufacturing schedule. The proposed research provides a new rescheduling method and helps instruct scheduler to make production planning in hull block construction.     

SWARM INTELLIGENCE BASED DYNAMIC REAL-TIME SCHEDULING APPROACH FOR SEMICONDUCTOR WAFER FAB

Based on the analysis of collective activities of ant colonies, the typical example of swarm intelligence, a new approach to construct swarm intelligence based multi-agent-system (SMAS) for dynamic real-time scheduling for semiconductor wafer fab is proposed. The relevant algorithm, pheromone-based dynamic real-time scheduling algorithm (PBDR), is given. MIMAC test bed data set mini-fab is used to compare PBDR with FIFO (first in first out), SRPT(shortest remaining processing time) and CR(critical ratio) under three different release rules, i.e. deterministic rule, Poisson rule and CONWIP (constant WIP). It is shown that PBDR is prior to FIFO, SRPT and CR with better performance of cycle time, throughput, and on-time delivery, especially for on-time delivery performance.     

Dynamic topology multi force particle swarm optimization algorithm and its application

Particle swarm optimization(PSO) algorithm is an effective bio-inspired algorithm but it has shortage of premature convergence. Researchers have made some improvements especially in force rules and population topologies. However, the current algorithms only consider a single kind of force rules and lack consideration of comprehensive improvement in both multi force rules and population topologies. In this paper, a dynamic topology multi force particle swarm optimization(DTMFPSO) algorithm is proposed in order to get better search performance. First of all, the principle of the presented multi force particle swarm optimization(MFPSO) algorithm is that different force rules are used in different search stages, which can balance the ability of global and local search. Secondly, a fitness-driven edge-changing(FE) topology based on the probability selection mechanism of roulette method is designed to cut and add edges between the particles, and the DTMFPSO algorithm is proposed by combining the FE topology with the MFPSO algorithm through concurrent evolution of both algorithm and structure in order to further improve the search accuracy. Thirdly, Benchmark functions are employed to evaluate the performance of the DTMFPSO algorithm, and test results show that the proposed algorithm is better than the well-known PSO algorithms, such as μPSO, MPSO, and EPSO algorithms. Finally, the proposed algorithm is applied to optimize the process parameters for ultrasonic vibration cutting on Si C wafer, and the surface quality of the Si C wafer is improved by 12.8% compared with the PSO algorithm in Ref. [25]. This research proposes a DTMFPSO algorithm with multi force rules and dynamic population topologies evolved simultaneously, and it has better search performance.     

多目标模糊作业车间调度问题研究

研究了具有模糊加工时间和模糊交货期的多目标作业车间调度问题，首先给出了基于模糊优先规则的编码新方式，染色体的每一位表示在GT算法迭代过程中，对应机器上发生的某次冲突，根据该基因位对应的优先规则消除。然后设计了基于个体密集距离的多目标进化算法，该算法利用密集距离进行外部档案维护和适应度赋值。最后将多目标进化算法应用于模糊作业车间调度问题，以最大化最小一致指标和最小化模糊最大完成时间，并和其他算法比较。计算结果验证了多目标进化算法在模糊调度方面良好的搜索性能。     

Crowding-measure-based multiobjective evolutionary algorithm for job shop scheduling

Multiobjective evolutionary algorithm (MOEA) has attracted much attention in the past decade; however, the application of MOEA to practical problems such as job shop scheduling is seldom considered. In this paper, crowding-measure-based multiobjective evolutionary algorithm (CMOEA) is first designed, which makes use of the crowding measure to adjust the external population and assign different fitness for individuals; then CMOEA is applied to job shop scheduling to minimize makespan and the total tardiness of jobs. Finally, the comparison between CMOEA and SPEA demonstrates that CMOEA performs well in job shop scheduling.     

Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems

This paper addresses multi-objective job shop scheduling problems with fuzzy processing time and due-date in such a way to provide the decision-maker with a group of Pareto optimal solutions. A new priority rule-based representation method is proposed and the problems are converted into continuous optimization ones to handle the problems by using particle swarm optimization. The conversion is implemented by constructing the corresponding relationship between real vector and the chromosome obtained with the new representation method. Pareto archive particle swarm optimization is proposed, in which the global best position selection is combined with the crowding measure-based archive maintenance, and the inclusion of mutation into the proposed algorithm is considered. The proposed algorithm is applied to eight benchmark problems for the following objectives: the minimum agreement index, the maximum fuzzy completion time and the mean fuzzy completion time. Computational results demonstrate that the proposal algorithm has a promising advantage in fuzzy job shop scheduling.     

A deadlock-free scheduling with sequence-dependent setup times

This paper presents a novel approach to job shop scheduling with sequence-dependent setup times. The scheduling modeling is based on timed Petri nets. Control arcs are introduced to alleviate deadlocks, thus ensuring sequence-dependent setups. Based on siphon-related truncation, an efficient branch and bound algorithm for deadlock-free scheduling is devised. In addition, an effective priority rule is defined to handle large-scale problems. A series of experiments illustrate the validity of the priority rule and the scalability of our method for large-scale problems.     

基于蚁群算法的模具制造动态调度研究

为解决模具制造动态调度问题，建立了动态调度系统。该系统利用蚁群算法和优先分配启发式算法相结合的调度算法，解决具有工件约束的模具零件的调度问题。该算法首先由蚁群算法确定模具零件各工序所用加工机床，然后利用优先分配启发式算法确定在同一台机床上加工的各零件的先后顺序。考虑动态调度的实时性，提出了局部更新和全局更新相结合的、基于滑动窗口机制的动态调度方法。对于发生频率高但对调度计划执行影响不大的扰动事件采用局部更新策略，反之则采用全局更新策略，在保证获得近优解的同时提高了动态调度的效率。     

基于汽车电子网络的CAN总线简化型混合调度算法

现有的控制器局域网（CAN）总线调度算法性能不能很好地满足汽车电子网络化发展的需要,针对这一问题,首先分析了现有CAN总线网络节点消息优先级调度算法的优缺点,然后针对CAN总线网络在汽车电子控制网络系统中的特点,在混合调度（MTS）算法的基础上提出了一种简化型混合调度（EMTS）算法。仿真实验结果表明,该简化算法能达到原算法的性能,在节点消息截止期相近的情况下,其调度性能比MTS算法有所提高。     

基于混合调度算法汽车TTCAN网络设计及实时性分析

针对汽车控制系统CAN总线在处理周期性信号和随机性信号时具有不确定性和信息易死锁等缺陷问题,把服务于时间触发的均匀装载(AL)算法和服务于事件触发的动态优先级提升(DPP)算法相结合,提出了一种基于时间触发的控制器局域网(TTCAN)协议的混合调度策略,介绍了混合调度算法原理及实时性分析方法,构建了基于混合算法的汽车TTCAN系统矩阵,通过应用实例分析,验证了该方案满足汽车控制系统的实时性要求.     

基于强化学习的分布式光伏运维资源动态调度

针对分布式光伏运维资源调度过程中因动态因素影响导致调度计划难以实施的问题,提出基于强化学习的分布式光伏运维资源动态调度方法。该方法通过构建动态调度规则同步调整运维任务的优先级,并以新计划完成成本最低和完成时间最短为优化目标构建动态调度模型。采用Q-Learning求解模型,通过实验对比,Q-Learning算法的求解速度快、算法稳定性好,更适合求解动态调度问题,所提资源动态调度方法可以应对分布式光伏运维过程中的动态因素影响,提升服务质量。     

求解资源受限多项目调度的改进遗传规划算法

针对优先级规则调度不具备优化能力的缺陷，提出了一种应用于资源受限多项目调度的改进超启发式遗传规划算法以进化出更理想的优先级规则。通过分析现有优先级规则构建出适用多项目调度的归一化属性集和顶层判别编码方式，并结合NSGA-Ⅱ虚拟适应度分配方法对种群进行评估以实现多目标优化。设计了一种多样性种群更新方式，以避免传统遗传规划易陷入局部最优的缺陷和提高搜索能力。通过基于标准数据集PSPLIB所构造的算例和飞机总装装配线的生产实例验证了该方法的有效性和可行性。     

基于瓶颈分析的优先权调度算法研究

制造执行系统在制造系统中的广泛应用,为实现生产车间的动态实时调度提供了可能性,也对实时调度算法提出了更高的要求。调度算法必须在考虑求解速度的前提下来求得满意解。根据优化生产技术的解决车间调度问题的思想,基于转移瓶颈启发式算法,提出了一种基于瓶颈分析的优先权调度算法,用于解决制造执行系统中的动态实时调度问题。