考虑交货期和等待时间受限的HFS调度问题的混合算法

针对工件具有交货期要求以及等待时间受限的混合流水车间调度问题,提出了一种回溯、启发式修复与邻域搜索相结合的混合算法.工件按启发式规则形成加工序列,以排列排序方式经过各加工阶段,采用递归回溯消除工件在相邻阶段的等待时间受限冲突,形成所有机器上的操作加工序列;通过对最后阶段机器上的操作加工序列进行移动修复以最小化其提前/拖期成本;对工件排序进行邻域搜索以改进目标函数值.数据实验表明该混合算法具有可行性和有效性.     

带恶化工件的PFS调度的混合遗传算法北大核心CSSCI

研究了带恶化工件的置换流水车间调度问题,其中工件的加工时间是与开始时间有关的线性函数,考虑不同工件在不同机器上具有不同的恶化率,以最小化最大完工时间为目标,建立数学规划模型,进而提出了一种混合遗传算法来求解。该算法引入一种启发式规则以产生m-1条染色体改进初始种群的40%,结合遗传算法的初始种群产生方法共同生成种群,设计遗传参数自适应调节。仿真实验测试和对比了启发式法、遗传算法和混合遗传算法三种求解方法,实验结果表明所提出的混合遗传算法能更有效地求解这类NP-hard问题。     

带恶化工件的PFS调度的混合遗传算法

研究了带恶化工件的置换流水车间调度问题,其中工件的加工时间是与开始时间有关的线性函数,考虑不同工件在不同机器上具有不同的恶化率,以最小化最大完工时间为目标,建立数学规划模型,进而提出了一种混合遗传算法来求解。该算法引入一种启发式规则以产生m-1条染色体改进初始种群的40%,结合遗传算法的初始种群产生方法共同生成种群,设计遗传参数自适应调节。仿真实验测试和对比了启发式法、遗传算法和混合遗传算法三种求解方法,实验结果表明所提出的混合遗传算法能更有效地求解这类NP-hard问题。     

基于CSP的钢铁企业订单投放与指派方法研究

针对钢铁生产中订单投放问题,建立数学模型,提出了度量拖期程度、负荷均衡程度两个指标。利用约束满足技术中灵活的变量选择和值选择规则以及约束传播技术对经典订单投放方法和指派规则进行改进,提出了基于瓶颈优先和负荷均衡的订单投放方法和改进的EDD指派规则。其中选择符合时间与负荷约束的订单进行投放,将工作量均匀加载到机器负荷;在指派生产顺序时,兼顾订单交货期和加工时长,优化可能拖期的订单生产顺序。针对不同投放方法与指派规则的组合,以及订单投放效果影响因素设计实验,结果表明模型与算法具有可行性与有效性。     

无空闲占优机器的加工时间可变流水作业排序

研究了基于实际应用背景提炼出的工件加工时间是其开工时间的线性函数的无空闲流水作业排序问题。在机器分别具有某些优势关系的情形下,探讨了目标函数为极小化最大完工时间和极小化总完工时间之和的情况。对于每种情况,分别给出了工件按某种规则排序为最优序的多项式时间算法。     

一种单机加权成套订单数问题的遗传算法

在基本的单机加权成套订单数问题[1]研究的基础上,增加考虑加工工件具有多种类型,且同类工件可分开加工,不同类工件之间接连加工需要机器调整时间的情况.建立了该类问题的0-1整数规划模型,设计求解该类问题的遗传算法,并通过一个算例对这类排序问题和所提出的算法进行说明.算法在文中所列三种初始种群规模下的10次运算内都能得到算例的最优解0.77,每次运算大都在100代以内得到收敛,多次试验结果显示算法具有较强的寻优功能、收敛平稳且运算时间较短,表明了算法求解此类问题的有效性.     

考虑工序并行的差异工件批调度研究

针对铸造车间差异工件组批多约束的问题,在工序可并行加工的前提下构建以最小化最大完工时间和最小化沙箱空置率为优化目标的并行工序批调度模型,设计一种改进和声算法求解该调度模型,提出一种单工序编解码方式和2种机器分配规则用于解决工件分批、沙箱选择、工序分配及机器选择的问题。在算法中提出一种新的和声产生方式和更新机制,同时为改善算法的局部搜索能力,加入模拟退火算法执行局部搜索过程。最后根据企业实际生产数据进行仿真实验,验证本文模型的有效性。     

基于混合离散人工蜂群算法的混合零等待柔性流水车间优化研究

从钢铁业等流程工业提炼出一类混合零等待柔性流水车间问题，其中一些加工阶段要求工件连续不断地经过这些工序，对该问题建立了整数规划模型，提出了一种混合离散人工蜂群算法以最小化最大完工时间。采用二维矩阵编码表述染色体以及工件右移调整策略进行解码以获取调度解，改进NEH启发式规则用于生成初始种群。在雇佣蜂阶段，引入了修正粒子群优化算法产生新解；在跟随蜂阶段，设计了迭代贪婪算法中的破坏和构造算子，进一步增强算法的搜索能力；在侦查蜂阶段，利用变邻域搜索算子以替换最差解。对不同规模问题进行了仿真测试并与现有算法进行对比，结果表明所提算法在求解混合零等待柔性流水车间问题方面更加有效。     

基于最早开工时间疫苗的免疫遗传算法求解JSP

车间调度通过在设备上合理安排工件的加工队列,提高产品加工的生产力及设备利用率。本文在免疫遗传算法中,设计了最早开工时间疫苗后对单件车间问题进行优化。疫苗提取时,将工件在机器上以最早开工原则直接安排其加工顺序,提取所有机器上的工件加工队列为疫苗;接种时,按照待接种个体的机器码将疫苗信息依次接种到对应的机器位置。最后采用标准案例测试,经结果分析可知所设计算法求解性能良好。     

改进离散候鸟优化算法求解带缺失阶段的柔性流水车间问题

针对每阶段包含不相关并行机的柔性流水车间调度，研究了具有缺失阶段的总加权完工时间问题。由于该问题是NP-hard的，因此，提出基于两段式编码和组合邻域策略的改进离散候鸟优化算法进行求解。基于机器和工件编号设计两段式编码，利用最短加工时间规则和随机策略获得初始候鸟种群。领飞鸟和跟飞鸟进化中引入组合邻域策略以产生邻域解，最后对最差个体设计重置机制以再次提高解的质量。针对不同规模问题，对所提算法和四种启发式算法进行仿真实验，实验结果表明改进离散候鸟优化算法得到了更高质量的满意解。     

A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines

This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines at stage 2. The objective is to minimise the makespan. There is one machine at stage 1 and two machines at stage 2. Each job must be processed on the single machine at stage 1 and, depending upon the job type, the job is processed on either of the two machines at stage 2. We first introduce this special type of the two-stage hybrid flow shop scheduling problem and present some preliminary results. We then present a counter example to the known complexity proof of Riane et al. [Riane, F., Artiba, A. and Elmaghraby, S.E., 2002. Sequencing a hybrid two-stage flowshop with dedicated machines. International Journal of Production Research, 40, 4353–4380.] Finally, we re-establish the complexity of the problem.     

Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method

This paper investigates an integrated bi-objective optimisation problem with non-resumable jobs for production scheduling and preventive maintenance in a two-stage hybrid flow shop with one machine on the first stage and m identical parallel machines on the second stage. Sequence-dependent set-up times and preventive maintenance (PM) on the first stage machine are considered. The scheduling objectives are to minimise the unavailability of the first stage machine and to minimise the makespan simultaneously. To solve this integrated problem, three decisions have to be made: determine the processing sequence of jobs on the first stage machine, determine whether or not to perform PM activity just after each job, and specify the processing machine of each job on the second stage. Due to the complexity of the problem, a multi-objective tabu search (MOTS) method is adapted with the implementation details. The method generates non-dominated solutions with several parallel tabu lists and Pareto dominance concept. The performance of the method is compared with that of a well-known multi-objective genetic algorithm, in terms of standard multi-objective metrics. Computational results show that the proposed MOTS yields a better approximation.     

Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times

This paper studies the makespan minimisation scheduling problem in a two-stage hybrid flow shop. The first stage has one machine and the second stage has m identical parallel machines. Neither the processing time nor probability distribution of the processing time of each job is uncertain. We propose a robust (min–max regret) scheduling model. To solve the robust scheduling problem, which is NP-hard, we first derive some properties of the worst-case scenario for a given schedule. We then propose both exact and heuristic algorithms to solve this problem. In addition, computational experiments are conducted to evaluate the performance of the proposed algorithms.     

A hybrid electromagnetism-like algorithm for two-stage assembly flow shop scheduling problem

This paper presents a study on the two-stage assembly flow shop scheduling problem for minimising the weighed sum of maximum makespan, earliness and lateness. There are m machines at the first stage, each of which produces a component of a job. A single machine at the second stage assembles the m components together to complete the job. A novel model for solving the scheduling problem is built to optimise the maximum makespan, earliness and lateness simultaneously. Two optimal operation sequences of jobs are determined and verified. As the problem is known to be NP-hard, a hybrid variable neighbourhood search – electromagnetism-like mechanism (VNS-EM) algorithm is proposed for its handling. To search beyond local optima for a global one, VNS algorithm is embedded in each iteration of EM, whereby the fine neighbourhood search of optimum individuals can be realised and the solution is thus optimised. Simulation results show that the proposed hybrid VNS-EM algorithm outperforms the EM and VNS algorithms in both average value and standard deviation.     

A genetic algorithm for the multi-stage and parallel-machine scheduling problem with job splitting – A case study for the solar cell industry

This paper studies a multi-stage and parallel-machine scheduling problem with job splitting which is similar to the traditional hybrid flow shop scheduling (HFS) in the solar cell industry. The HFS has one common hypothesis, one job on one machine, among the research. Under the hypothesis, one order cannot be executed by numerous machines simultaneously. Therefore, multiprocessor task scheduling has been advocated by scholars. The machine allocation of each order should be scheduled in advance and then the optimal multiprocessor task scheduling in each stage is determined. However, machine allocation and production sequence decisions are highly interactive. As a result, this study, motivated from the solar cell industry, is going to explore these issues. The multi-stage and parallel-machine scheduling problem with job splitting simultaneously determines the optimal production sequence, multiprocessor task scheduling and machine configurations through dynamically splitting a job into several sublots to be processed on multiple machines. We formulate this problem as a mixed integer linear programming model considering practical characteristics and constraints. A hybrid-coded genetic algorithm is developed to find a near-optimal solution. A preliminary computational study indicates that the developed algorithm not only provides good quality solutions but outperforms the classic branch and bound method and the current heuristic in practice.     

Variable neighbourhood search for minimising tardiness objectives on flow shop with batch processing machines

This paper presents the scheduling problem on flow shop with many batch processing machines (BPM) to minimise total tardiness, maximum tardiness and number of tardy jobs, respectively. We propose an efficient variable neighbourhood search (VNS) for the problem, in which job permutation is the only optimisation object and the solutions of batch formation and batch scheduling can be directly obtained by using the permutation. To obtain the promising results, an initial solution of VNS is first produced and then one insertion operation and two swap operations are applied to improve the solution. The proposed VNS is finally tested and the computational results show its good performance on many-BPM flow shop scheduling.     

Dynamic job shop scheduling using variable neighbourhood search

In this paper a scheduling method based on variable neighbourhood search (VNS) is introduced to address a dynamic job shop scheduling problem that considers random job arrivals and machine breakdowns. To deal with the dynamic nature of the problem, an event-driven policy is selected. To enhance the efficiency and effectiveness of the scheduling method, an artificial neural network with a back propagation error learning algorithm is used to update parameters of the VNS at any rescheduling point according to the problem condition. The proposed method is compared with some common dispatching rules that have been widely used in the literature for the dynamic job shop scheduling problem. Results illustrate the high efficiency and effectiveness of the proposed method in a variety of shop floor conditions.     

A priority scheduling approach for flexible job shops with multiple process plans

This paper considers the job shop scheduling problem with alternative operations and machines, called the flexible job shop scheduling problem. As an extension of previous studies, operation and routing flexibilities are considered at the same time in the form of multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. Since the problem is highly complicated, we suggest a practical priority scheduling approach in which the two decisions are done at the same time using a combination of operation/machine selection and job sequencing rules. The performance measures used are minimising makespan, total flow time, mean tardiness, the number of tardy jobs, and the maximum tardiness. To compare the performances of various rule combinations, simulation experiments were done on the data for hybrid systems with an advanced reconfigurable manufacturing system and a conventional legacy system, and the results are reported.     

Hybrid simulated annealing with memory: an evolution-based diversification approach

This study presents an efficient metaheuristic approach for combinatorial optimisation and scheduling problems. The hybrid algorithm proposed in this paper integrates different features of several well-known heuristics. The core component of the proposed algorithm is a simulated annealing module. This component utilises three types of memories, one long-term memory and two short-term memories. The main characteristics of the proposed metaheuristic are the use of positive (reinforcement) and negative (inhibitory) memories as well as an evolution-based diversification approach. Job shop scheduling is selected to evaluate the performance of the proposed method. Given the benchmark problem, an extended version of the proposed method is also developed and presented. The extended version has two distinct features, specifically designed for the job shop scheduling problem, that enhance the performance of the search. The first feature is a local search that partially explores alternative solutions on a critical path of any current solution. The second feature is a mechanism to resolve possible deadlocks that may occur during the search as a result of shortage in acceptable solutions. For the case of job shop scheduling, the computational results and comparison with other techniques demonstrate the superior performance of the proposed methods in the majority of cases.     

Linguistic-based meta-heuristic optimization model for flexible job shop scheduling

In this paper, a linguistic based meta-heuristic modelling and solution approach for solving the Flexible Job Shop Scheduling Problem (FJSSP) is presented. FJSSP is an extension of the classical job-shop scheduling problem. The present problem definition is to assign each operation to a machine out of a set of capable machines ( the routing problem ) and to order the operations on the machines ( the sequencing problem ), such that a predefined performance measure is optimized. The scope of the problem is widened by taking into account the alternative process plans for each part ( process plan selection problem ) in the present study. Moreover, instead of using operations to represent product processing requirements and machine processing capabilities, machine independent capability units, which are known as Resource Elements (RE), are used. Representation of unique and shared capability boundaries of machine tools and part processing requirements is possible via RE. Using REs in scheduling can also reduce the problem size. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls. Using these controls and the Giffler and Thompson (1960) priority rule-based heuristic, a simulated annealing algorithm is developed to solve FJSSP. This novel approach simplifies the modelling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its solution. The results obtained from the computational study have shown that the proposed algorithm can solve this complex problem effectively within reasonable time. The results have also given some insights on the effect of the selection of dispatching rules and the flexibility level on the job shop performance. It is observed that the effect of dispatching rule selection on the job shop performance diminishes by increasing the job shop flexibility.