一种混合遗传算法在车间作业调度中的应用研究

结合遗传算法和局域搜索的优点,提出一种混合遗传算法(HGA)以解决Job-shop调度问题。HGA采用基于工序的编码方案;然后在探讨影响HGA性能的交叉和变异算子的基础上,引入顺序保留交叉算子(PPX),并采用具有邻域搜索能力的变异算子;最后应用局部搜索对得到的GA解进行微调以改善解的质量。仿真结果表明了本文方法的有效性。     

基于JIT的非等同并行多机调度问题的混合遗传算法

针对一类NP完全问题的多目标、非等同、并行多机作业调度问题,设计了一个混合遗传算法。该算法在设计过程中针对该问题的特点,设计了一种动态适应度函数;将求解单机问题最优解的有效算法混合在编码方案中,设计了一种不包括作业顺序的简单编码方案,从而降低了算法的实现难度,并提高了执行效率。数值仿真实验表明,该算法具有收敛速度快、优化效果好等特点,适合于求解较大规模的问题。     

订单型企业多目标生产计划的制定及其调度

针对制定订单式小批量生产计划问题,提出了一种使用动态随机投入产出函数来制定多目标生产计划的方法。针对生产调度问题,提出了联合使用最长加工时间优先(LPT)与遗传算法(GA)的混合遗传算法(HGA)来求解混合流水线的调度,并给出了一种新的编码方法,选择了相应的交叉和变异方法。研究结果表明,该计划制造方法能较好地满足订单型企业的随机性要求,而且生产计划编制效率高。该编码方法在保证染色体合法性的同时也保证了算法本身的随机性。某轧辊厂的实际案例分析结果也验证了所提出的订单型企业多目标生产计划的制定及其调度方法的可行性。     

Parallel machine scheduling with earliness-tardiness penalties and space limits

In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.     

带变异算子的启发式最大最小蚂蚁系统求解流水车间调度问题

针对蚂蚁算法在求解流水车间调度问题(FSP)时易出现停滞以及计算时间较长的缺点,对最大最小蚂蚁系统(MMAS)进行了改进,提出一种带变异算子的启发式最大最小蚂蚁系统,在改进的算法中,指出了启发式信息值的求法,对一些参数作动态性调整并融入了遗传算法中的变异操作,最后,通过仿真结果表明了该算法对求解FSP问题是有效的。     

Integrated optimization of production planning and scheduling for a kind of job-shop

This paper addresses an integrated job-shop production planning and scheduling problem with setup time and batches. It not only considers the setup cost, work-in-process inventory, product demand, and the load of equipment, but also the detailed scheduling constraints. That is a way different from the traditional hierarchical production planning method. The hierarchical methods do not consider the detailed scheduling constraints, so it cannot guarantee to obtain a feasible production plan. Here the integrated problem is formulated as a nonlinear mixed integer program model. And in order to simultaneously optimize the production plan and the schedule, an improved hybrid genetic algorithm (HGA) is given. In the model, the detailed scheduling constraints are used to compute the accurate load of a device in order to obtain a feasible production plan. The heuristic scheduling rules such as the shortest processing time (SPT) and the longest processing time (LPT) are used to generate a better initial solution. Also, a subsection coding strategy is offered to convert the planning and scheduling solution into a chromosome. At last, a comparison is made between the hybrid algorithm and a hierarchical production planning and scheduling method, showing that the hybrid algorithm can solve the problem effectively.     

自动化仓库旋转货架拣选优化

对自动化仓库旋转货架拣选优化问题进行了描述,提出了求解该问题的分层遗传算法（HGA）。根据具体问题对低层和高层采用了不同的进化策略,详细介绍了HGA算法的原理。通过实际算例运算及分析,表明HGA对解决自动化仓库旋转货架拣选优化问题的有效性。     

多目标柔性作业车间调度决策精选机制研究

针对多目标柔性作业车间调度优化无法找到唯一最优解的问题，提出多目标遗传算法和层次分析法模糊综合评判的分阶段优化策略。提出优化阶段和精选阶段的优化任务，优化阶段选出一组Pareto解集，精选阶段从Pareto解集中选出最优解；在精选阶段运用层次分析法和模糊评判集成的策略精选调度决策。决策算例证明提出的方法是可行的，可很好地帮助决策者选择出一个最满意的解。     

Optimization of PCB component placements for the collect-and-place machines

This paper presents two hybrid genetic algorithms (HGAs) to optimize the component placement operation for the collect-and-place machines in printed circuit board (PCB) assembly. The component placement problem is to optimize (i) the assignment of components to a movable revolver head or assembly tour, (ii) the sequence of component placements on a stationary PCB in each tour, and (iii) the arrangement of component types to stationary feeders simultaneously. The objective of the problem is to minimize the total traveling time spent by the revolver head for assembling all components on the PCB. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method, the nearest neighbor heuristic, and the neighborhood frequency heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different population sizes. It is proved that the performance of HGA2 is superior to HGA1 in terms of the total assembly time.     

基于混合遗传算法的柔性制造系统优化设计

针对基于闭排队网络模型的柔性制造系统优化设计问题，提出了一种混合遗传算法，利用该模型中生产量函数和成本函数的单调性，设计了最大产量－成本梯度算子，来引导新一代种群从不可行域进入可行域，既实现了利用遗传算法求解柔性制造系统约束优化问题，又增强了遗传算法的局部搜索能力。由于该算法利用渐近边界分析思想和编码技术减少了计算量，从而使混合遗传算法既保持了遗传算法的全局寻优特点，又提高了运行效率。算例证明，该算法的求解质量优于目前该领域常用的隐枚举算法。     

基于混合遗传算法的桥梁颤振导数识别

提出一种基于混合遗传算法识别桥梁颤振导数的方法,该混合遗传算法将模拟退火算法与遗传算法相结合,充分利用遗传算法的并行运算机制以及模拟退火算法的强局部搜索机制,具有较强的鲁棒性和全局收敛性,从而保证识别的精度。该方法通过对自由振动时程曲线进行时域拟合,识别出自由振动表达式中的各参数,进而确定系统的等效刚度矩阵和等效阻尼矩阵,并同时得到8个颤振导数。数值仿真算例表明该方法的可靠性,风洞试验表明该方法有效、可行。     

基于混合遗传算法的工艺路线优化配置

针对 FMS工艺路线优化配置问题提出一种混合遗传算法。该算法在遗传算法中引入了具有启发式规则的余量随机分配算子 ,可以将超过约束条件的余量随机分配到个体中去 ,通过按照一定规则的调整而将不可行个体引入可行域。一方面实现了利用遗传算法求解工艺路线的约束优化问题 ,保持了遗传算法的全局寻优特点 ,另一方面加强了遗传算法的局部搜索能力 ,提高了运行效率。算例证明该算法的求解效果好于目前该领域常用的启发式算法。     

A genetic algorithmic approach to multi-objective scheduling in a kanban-controlled flowshop with intermediate buffer and transport constraints

In this paper, we consider the problem of extended permutation flowshop scheduling with the intermediate buffers. The Kanban flowshop problem considered involves dual-blocking by both part type and queue size acting on machines, as well as on material handling. The objectives considered in this study include the minimization of mean completion time of containers, mean completion time of part types, and the standard deviation of mean completion time of part types. An attempt is made to solve the multi-objective problem by using a proposed genetic algorithm, called the “non-dominated and normalized distanceranked sorting multi-objective genetic algorithm” (NDSMGA). In order to evaluate the NDSMGA, we have made use of randomly generated flowshop scheduling problems with input and output buffer constraints in the flowshop. The non-dominated solutions for these problems are obtained from each of the existing methods, namely multi-objective genetic local search (MOGLS), elitist non-dominated sorting genetic algorithm (ENGA), gradual priority weighting genetic algorithm (GPWGA), modified MOGLS, and the NDSMGA. These non-dominated solutions are combined to obtain a net non-dominated solution set for a given problem. Contribution in terms of number of solutions to the net non-dominated solution set from each of these algorithms is tabulated, and the results reveal that a substantial number of non-dominated solutions are contributed by the NDSMGA.     

A dispatching rule-based hybrid genetic algorithm focusing on non-delay schedules for the job shop scheduling problem

Job shop scheduling is an important decision process in contemporary manufacturing systems. In this paper, we aim at the job shop scheduling problem in which the total weighted tardiness must be minimized. This objective function is relevant for the make-to-order production mode with an emphasis on customer satisfaction. In order to save the computational time, we focus on the set of non-delay schedules and use a genetic algorithm to optimize the set of dispatching rules used for schedule construction. Another advantage of this strategy is that it can be readily applied in a dynamic scheduling environment which must be investigated with simulation. Considering that the rules selected for scheduling previous operations have a direct impact on the optimal rules for scheduling subsequent operations, Bayesian networks are utilized to model the distribution of high-quality solutions in the population and to produce the new generation of individuals. In addition, some selected individuals are further improved by a special local search module based on systematic perturbations to the operation processing times. The superiority of the proposed approach is especially remarkable when the size of the scheduling problem is large.     

A genetic algorithmic approach to multi-objective scheduling in a Kanban-controlled flowshop with intermediate buffer and transport constraints

In this paper, we consider the problem of extended permutation flowshop scheduling with the intermediate buffers. The Kanban flowshop problem considered involves dual-blocking by both part type and queue size acting on machines, as well as on material handling. The objectives considered in this study include the minimization of mean completion time of containers, mean completion time of part types, and the standard deviation of mean completion time of part types. An attempt is made to solve the multi-objective problem by using a proposed genetic algorithm, called the “non-dominated and normalized distance-ranked sorting multi-objective genetic algorithm” (NDSMGA). In order to evaluate the NDSMGA, we have made use of randomly generated flowshop scheduling problems with input and output buffer constraints in the flowshop. The non-dominated solutions for these problems are obtained from each of the existing methods, namely multi-objective genetic local search (MOGLS), elitist non-dominated sorting genetic algorithm (ENGA), gradual priority weighting genetic algorithm (GPWGA), modified MOGLS, and the NDSMGA. These non-dominated solutions are combined to obtain a net non-dominated solution set for a given problem. Contribution in terms of number of solutions to the net non-dominated solution set from each of these algorithms is tabulated, and the results reveal that a substantial number of non-dominated solutions are contributed by the NDSMGA.     

基于改进遗传算法的生产车间多工艺计划调度研究

建立了基于多工艺加工计划的生产调度数学模型,给出了基于改进遗传算法的无辅助加工时间多工艺加工计划调度算法,通过与国外学者提出的算法相比较,证明了该算法的正确性和优越性,实验结果表明,模型是正确的,算法是有效的。     

A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes

Usually, most of the typical job shop scheduling approaches deal with the processing sequence of parts in a fixed routing condition. In this paper, we suggest a genetic algorithm (GA) to solve the job-sequencing problem for a production shop that is characterized by flexible routing and flexible machines. This means that all parts, of all part types, can be processed through alternative routings. Also, there can be several machines for each machine type. To solve these general scheduling problems, a genetic algorithm approach is proposed and the concepts of virtual and real operations are introduced. Chromosome coding and genetic operators of GAs are defined during the problem solving. A minimum weighted tardiness objective function is used to define code fitness, which is used for selecting species and producing a new generation of codes. Finally, several experimental results are given.     

Scheduling in a two-machine flow-shop for earliness/tardiness under learning effect

In the literature, earliness/tardiness (E/T) problem was known as weighted absolute deviation problem, and both tardiness and earliness is very important performance criteria for scheduling problem. While total tardiness criteria provides adaptation for due date (ignoring results of earliness done jobs), it deals with only cost of tardiness. However this phenomenon has been started to change with just-in-time (JIT) production concept. On JIT production, earliness is as important as tardiness. The phenomenon of the learning effect has been extensively studied in many different areas of operational research. However, there have been a few studies in the general context of production scheduling such as flow-shop scheduling. This paper addresses the minimization of the total earliness/tardiness penalties under learning effects in a two-machine flow-shop scheduling problem. Jobs have a common due date. We present mathematical model to obtain an optimal schedule for a given job sequence. We also present heuristics that use genetic algorithm and tabu search, based on proposed properties. Furthermore, random search was used for showing the significance of the study by comparison purpose. A new set of benchmark problems is presented with the purpose of evaluating the heuristics. The experimental results show that the performance of proposed approach is quite well, especially for the instances of large size.     

Multiple cycle economic lot and delivery-scheduling problem in a two-echelon supply chain

This paper addresses the problem of lot sizing, scheduling, and delivery of several items in a two-echelon supply chain over a finite planning horizon. Single supplier produces the items through a flexible flow line and delivers them directly to an assembly facility where the transfer of sub-lots between adjacent stages of supplier’s production system (i.e., lot streaming) is allowed in order to decrease the manufacturing lead time. At first, a mixed zero-one nonlinear programming model is developed based on the so-called basic period (BP) approach aiming to minimize the average setup, inventory holding, and delivery costs per unit time in the supply chain without any stock-out. The problem is very complex and cannot be solved to optimality especially for real-sized problems. Therefore, two efficient hybrid genetic algorithms (HGA) are proposed based on the power-of-two (PTHGA) and non-power-of-two (NPTHGA) variants of BP approach. The solution qualities of the proposed algorithms are compared with a proposed lower bound. Numerical experiments demonstrate that the NPTHGA outperforms the PTHGA algorithm with respect to the solution quality, but the PTHGA outperforms the NPTHGA with respect to the computation time.     

Inverse estimation of properties for charring material using a hybrid genetic algorithm

Fire characteristics can be analyzed more realistically by using more accurate material properties related to the fire dynamics and one way to acquire these fire properties is to use one of the inverse property estimation techniques. In this study an optimization algorithm which is frequently applied for the inverse heat transfer problems is selected to demonstrate the procedure of obtaining fire properties of a solid charring material with relatively simple chemical structure. Thermal decomposition is occurred at the surface of the test plate by receiving the radiative energy from external heat sources and in this process the heat transfer through the test plate can be simplified by an unsteady one dimensional problem. The input parameters for the analyses are the surface temperature and mass loss rate of the char plate which are determined from the actual experiment of from the unsteady one-dimensional analysis with a given set of eight properties. The performance of hybrid genetic algorithm (HGA) is compare with a basic genetic algorithm (GA) in order to examine its performance. This comparison is carried out for the inverse property problem of estimating the fire properties related to the reaction pyrolysis of some relatively simple materials; redwood and red oak. Results show that the hybrid genetic algorithm has better performance in estimating the eight pyrolysis properties than the genetic algorithm.