考虑批量装配的柔性作业车间调度问题研究

柔性作业车间调度是生产调度领域中的一个重要组合优化问题,由于取消了工序与加工设备的唯一性对应关系,因而相较于作业车间调度问题,具有更高的复杂度。针对该问题在批量装配方面的不足,考虑将批量因素与装配环节同时集成到柔性作业车间调度问题当中。以成品件的完工时间为优化目标,对该批量装配柔性作业车间调度问题进行了数学建模。针对该模型,提出一种多层编码结构的粒子群算法,并对该算法的各个模块进行了设计。最后,以实例验证了该数学模型的正确性及算法的有效性。     

批量生产柔性作业车间优化调度研究

在批量生产柔性作业车间调度问题中,不但要考虑路径选取和加工排序两个子问题,而且工件还可被分割为多个子批量,不同子批可选择不同工艺路线。该问题是对传统柔性作业车间调度问题(FJSP)的扩充,它更接近于实际生产调度问题。针对问题的特点,提出了一种基于遗传算法的柔性分批调度算法。在算法中,提出了一种基于"游标"的柔性批量分割方法,并采用一种批量分割与加工工序相融合的染色体编码方法。该算法不但可根据机床负荷将工件分割成具有柔性批量的多个子批,而且可使子批工艺路线选取及加工排序同时得到优化。通过实例仿真,对算法性能进行分析和评价,结果表明了算法的有效性和可行性。     

考虑准备时间和工件分批的柔性作业车间调度

针对柔性作业车间调度受生产准备时间和工件批量影响的问题,构建了考虑准备时间和工件分批的柔性作业车间调度模型.根据工件批量加工中等量分批方法柔性不足的特点,采用柔性分批方法对工件进行批量划分.提出一种改进的遗传算法,以最小化最大完工时间为优化目标,采用双层编码的方式对模型求解,确定各工件的分批方案和子批工序调度排序方案.通过分析柔性调度案例,验证了该算法的有效性,能够更好地满足实际车间生产要求.     

考虑约束松弛的柔性流水调度研究

针对柔性流水车间作业调度问题,考虑加工批量约束松弛和瓶颈工序顺序松弛2种情形,抽取出相应的新型柔性流水车间调度问题,建立了最小化最大完工时间的数学模型,提出了改进的单亲遗传算法,进行了优化求解,得到了不同约束松弛情况下的最优调度方案。通过算例仿真,验证了所提方法的有效性。     

柔性作业车间调度的改进邻域结构混合算法

针对柔性作业车间调度问题,以优化最大完工时间为目标,提出一种融合改进邻域结构的混合算法。柔性作业车间调度问题机器选择是工序排序优化的前提和基础,因此,将邻域结构分两级进行:第一级跨机器移动工序,第二级同机器移动工序。对同机器移动工序方面进行了改进,结合关键工序的类型定义了相应的移动操作,对已有邻域结构进行了无效移动的精简和有效移动的扩展,提高了邻域结构的精准有效性。给出了邻域结构相应的近似移动评价方法,综合考虑算法的全局搜索能力和局部搜索能力,设计了柔性作业车间调度问题求解算法。通过采用基准算例进行测试,验证了所提方法的有效性。     

柔性作业车间多品种小批量调度算法研究

提出一种多目标混合遗传算法(MIGA),采用集成法同时解决柔性作业车间调度的两个子问题:机器分配问题和工序调度问题。MIGA在标准遗传算法的基础上采用随机权重法解决多目标问题,引入精英保留策略加速算法的收敛,集成小生境技术提高种群的多样性,基于扩展工序编码,按Makespan和安装准备成本最优对调度批分别解码。最后,用标准算例进行了算法验证,证明MIGA可以有效解决柔性作业车间多品种小批量调度问题。     

柔性作业车间机床与搬运机器人联合调度方法

针对当前柔性作业车间机床和搬运机器人单独调度存在的不匹配问题,以车间完工时间为目标,提出基于多代竞争强进化遗传算法的机床与机器人联合调度方法。对多工件、多工序、多机床、多机器人的柔性作业车间联合调度问题进行了描述;考虑了机床生产和机器人搬运的时序约束,建立了最小化车间完工时间的优化模型;使用工序链、机床链及机器人链缠绕的染色体编码方式,将联合调度问题转化为算法优化问题;在遗传算法中引入多代竞争机理和强进化算子,其中多代竞争机理增加了优秀染色体的遗传概率,强进化算子具有保留优秀基因片段和强制差基因进化的能力。经生产实验验证,在15个工件44道工序的调度中,该算法的车间完工时间比标准遗传算法缩短了14.75%;另外,在不同规模的工件生产调度中,与克隆选择算法和标准遗传算法相比,该算法的迭代次数最少、车间完工时间最短。上述实验结果充分证明了多代竞争强进化遗传算法在柔性作业车间生产联合调度中的优越性。     

柔性作业车间批量划分与并行调度优化

针对柔性作业车间分批调度中因批次数量划分的随机性,导致最优分批方案存在搜索空间大、效率低的问题,提出试探法,使分批具有方向性、搜索空间可预测,从而得到合适的批量划分。进而提出相同工件同批工序间、不同工序间可并行的车间调度算法,与传统的批量调度结果相比,该算法可缩短生产周期、提高车间生产效率、减少批次数量、降低车间管理复杂度。采用上述方法对批次数量进行划分并使用并行算法对划分后的工序进行调度,实验结果表明,该方法在快速找到合适分批方案的同时优化了调度结果。     

基于规则的柔性作业车间机床与AGV联合调度优化

利用离散事件系统建模与仿真技术和规则调度方法,对柔性作业车间机床与AGV(automatic guided vehicle)联合调度问题进行研究。基于离散事件建模仿真方法建立了柔性作业车间仿真模型,以平均流动时间、完工时间、AGV平均利用率与完工数量为评价指标,首先将不同路由规则与调度规则组合结合AGV数量进行仿真测试,确定了最佳规则组合与AGV最佳数量。在确定最佳规则基础上,研究车间任务到达模式与AGV数量对系统性能的影响,不同工况下的仿真结果表明,在最优规则组合、任务到达模式与AGV数量下,柔性作业车间联合调度问题能得到有效解决且系统性能将达到最优。     

多目标柔性作业车间分批优化调度

为解决多目标柔性作业车间分批调度问题,提出了一种基于粒子群算法的多目标柔性分批调度算法。提出了一种基于游标的柔性批量分割方法,并采用一种批量分割与加工工序相融合的粒子编码方法,使得该算法不但可根据机床负荷将工件分割成具有柔性批量的多个子批,而且可使子批工艺路线选取及加工排序同时得到优化。算法引入了决策者的偏好信息,用于引导算法的搜索方向,使搜索结果集中于决策者感兴趣的Pareto边沿,避免了决策者在众多非劣解中做出困难选择。通过实例仿真,对算法性能进行了比较分析和评价,结果表明了算法的有效性和可行性。最后,从生产实际出发给出了算例,证明了算法的有效性和对生产实践的指导作用。     

Lot streaming in a two-machine mixed shop

Most classical scheduling models overlook the fact that products are often produced in job lots and assume that job lots are indivisible single entities, although an entire job lot consists of many identical items. However, splitting an entire lot (process batch) into sublots (transfer batches) to be moved to downstream machines allows the overlapping of different operations on the same product while work needs to be completed on the upstream machine. This approach is known as lot streaming in scheduling theory. In this study, the lot streaming problem of multiple jobs in a two-machine mixed shop where there are two different job types as flow shop and open shop is addressed so as to minimize the makespan. The optimal solution method is developed for the mixed shop scheduling problem in which lot streaming can improve the makespan.     

A study of the flexible job shop scheduling problem with parallel machines and reentrant process

This paper develops a scheduling algorithm for the job shop scheduling problem with parallel machines and reentrant process. This algorithm includes two major modules: the machine selection module (MSM) and the operation scheduling module (OSM). An order has several jobs and each job has several operations in a hierarchical structure. The MSM helps an operation to select one of the parallel machines to process it. The OSM is then used to schedule the sequences and the timing of all operations assigned to each machine. A real-life weapons production factory is used as a case study to evaluate the performance of the proposed algorithm. Due to the high penalty of delays in military orders, the on-time delivery rate is the most important performance measure and then makespan is the next most important measure. Well-known performance measures in the scheduling literature, such as maximum lateness and average tardiness, are also evaluated. The simulation results demonstrate that the MSM and OSM using the combination of earliest due date (EDD), the operations’ lowest level code (LLC) of the bill of materials (BOM), and the longest processing time (LPT) outperforms the other scheduling methods.     

Makespan minimization in a job shop with a BPM using simulated annealing

A scheduling problem commonly observed in the metal working industry has been studied in this research effort. A job shop equipped with one batch processing machine (BPM) and several unit-capacity machines has been considered. Given a set of jobs, their process routes, processing requirements, and size, the objective is to schedule the jobs such that the makespan is minimized. The BPM can process a batch of jobs as long as its capacity is not exceeded. The batch processing time is equal to the longest processing job in the batch. If no batches were to be formed, the scheduling problem under study reduces to the classical job shop problem with makespan objective, which is known to be nondeterministic polynomial time-hard. A network representation of the problem using disjunctive and conjunctive arcs, and a simulated annealing (SA) algorithm are proposed to solve the problem. The solution quality and run time of SA are compared with CPLEX, a commercial solver used to solve the mathematical formulation and with four dispatching rules. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using SA to solve large-scale problems.     

Scheduling of a hub reentrant job shop to minimize makespan

This paper focuses on a hub reentrant shop scheduling problem which is motivated by actual packing production line in the iron and steel industry. There are five operations for processing a job where three operations must be processed on a hub machine, and between any two consecutive operations on the hub machine, two operations must be processed on other two secondary machines, respectively. We mainly consider two types of the problem. The first is basic hub reentrant shop (BHRS) problem where only one machine in each secondary machine center. The second is hybrid hub reentrant shop (HHRS) problem where multiple machines in each secondary machine center. The objective is to minimize the makespan. For BHRS problem, we show that the problem is NP-hard in the strong sense. Some properties are derived for identifying an optimal schedule. Furthermore, a heuristic algorithm is proposed with the worst performance ratio 6:5, and this ratio is demonstrated tight. For HHRS problem, two well-solvable cases are proposed, respectively. Under a split condition, HHRS is equivalent to a two-stage hybrid flow shop problem. The worst case of a class of proposed algorithms is analyzed. The performance ratio is demonstrated relatively with the secondary machine numbers.     

Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling

In a proportionate flow shop problem, jobs have to be processed through a fixed sequence of machines, and processing time for each job is equal on all machines. Such a problem has seldom been tackled. Proportionate flexible flow shop (PFFS) scheduling problems combine the properties of proportionate flow shop scheduling problems and parallel machine scheduling problems. This study presents a combined approach based on column generation (CG) for a PFFS problem with the criterion to minimize the objective of the total weighted completion time (TWCT). Minimizing TWCT in a PFFS problem significantly differs from the parallel-identical-machine scheduling problem, an optimal schedule in which jobs on each machine are in the weighted shortest processing time (WSPT) order. This combined approach adopts a CG approach to effectively handle job assignments to machines, and a constructive heuristic to obtain an optimal sequence for a single machine. Experimental results show the effectiveness of the combined approach in obtaining excellent quality solutions in a reasonable time, especially for large-scale problems.     

A conflict-based priority dispatching rule and operation-based approaches to job shops

Job shop scheduling (JSS) problems consist of a set of machines and a collection of jobs to be scheduled. Each job consists of several operations with a specified processing order. In this paper, a job shop model problem is scheduled with the help of the Giffler and Thompson algorithm using a priority dispatching rule (PDR). A conflict based PDR is used to schedule the job shop model by using Genetic Algorithms (GAs). An iterative method is applied to the job model to find the optimal conflict-based PDR order and the operation sequence. The same job shop model is also scheduled based on an operation using simulated annealing (SA) and hybrid simulated annealing (HSA). A makespan of the job model is used as an objective. These four methods are considered as different solutions for each problem. A two-way analysis of variance (ANOVA) is applied to test its significance.     

Simulation optimization for a flexible jobshop scheduling problem using an estimation of distribution algorithm

The flexible jobshop scheduling problem permits the operation of each job to be processed by more than one machine. The idea is to assign the processing sequence of operations on the machines and the assignment of operations on machines such that the system objectives can be optimized. The assignment mentioned is a difficult task to implement on real manufacturing environments because there are many assumptions to satisfy, especially when the amount of work is not constant or sufficient to keep the manufacturing process busy for a long time, causing intermittent idle times. An estimation of distribution algorithm-based approach coupled with a simulation model is developed to solve the problem and implement the solution. Using the proposed approach, the shop performance can be noticeably improved when different machines are assigned to different schedules.     

Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date are given. The preemption of jobs is not permitted. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Firstly, several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. Then, genetic algorithms are suggested. We discuss the components of these algorithms and test their parameters. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages.     

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.     

基于过程集成的闭环动态工艺规划系统

描述了一个在过程上实现工艺规划与车间规划集成的闭环动态工艺规划系统,建立了实用化CAPP系统的新模型,丰富了动态CAPP的概念。它能根据车间环境的状态,充分利用制造工艺和车间环境的柔性产生优化的工艺方案。系统在车间环境约束下采用专家系统技术进行非线性工艺规划,产生可选工艺路线和工序可选设备。在一个由工艺路线选择、设备动态优化选择和车间优化规划构成的闭环系统中,以高生产效率为目标,根据推广的关键路线分析的结果和一系列启发式知识动态地选择工艺路线和设备,最后获得有较高实践意义的结果。