【作者】 展勇；

【导师】 邱长华；

【作者基本信息】 哈尔滨工程大学 ， 机械设计及理论， 2011， 博士

【摘要】 在制造领域,调度是生产管理的核心和关键技术,合理的调度可以缩短制造期、减少资源浪费,提高经济效益。随着生产过程的日益复杂和竞争的加剧,调度的作用越来越重要。柔性开放车间调度问题(FOSSP)是生产中常见的调度问题,也是亟待解决的高难度组合优化问题。本文主要研究加工可中断、不可中断和具有机器使用限制三种情况下的柔性开放车间调度问题(Om(P)|pmtn,ri|Cmax、Om(P)||Cmax和Om(P)|r,aN,I|Cmax)的数建模和近似调度算法设计。针对问题特点,分别采用网络流和半匹配理论设计了相应的近似调度算法,并给出了算法的最坏情况界等性能参数。本文主要研究内容包括以下五个方面：1.研究了柔性开放车间调度问题的数学建模方法。分析了可中断、不可中断和具有机器使用限制三种情况下柔性开放车间生产过程的约束条件,将它们形式化的表示为一组约束函数,以制造期最短为优化目标,建立了上述三种柔性开放车间调度问题的混合整数规划模型,为算法验证奠定了基础。2.以制造期最短为优化目标,给出了基于网络流的Om(P)|pmtn,ri|Cmax(?)司题调度算法。算法将Om(P)|pmtn,ri|Cmax问题分解为资源分配和工件排序两个子问题,首先将调度问题转化为网络流模型,通过最大流算法确定使机器满负荷工作的资源分配方案。为了提高最大流算法的效率,研究了融入加工领域知识的活跃顶点选择策略,采用最小负载优先和最大工作量优先启发式规则设计了高效率的最大流算法。针对最大流存在陷入局部优化的情况,给出了优化方法。在最大流的基础上,通过加工时间矩阵的减量集合确定工件的加工顺序3.针对Om(P)||Gmax问题求解难度大的特点,给出了以稠密调度为目标的近似调度算法求解方案,该方案将调度问题分解为资源匹配和调度优化两个子问题,每次资源匹配所有工件都仅完成一个操作,那么具有m个操作的工件集合需要进行m次资源匹配,通过连接各资源匹配结果得到初步调度解,最后对初步调度解进行优化,消除不必要的机器空闲时间,得到稠密调度解。在两个子问题中,资源匹配是核心问题,文中采用赋权二分图进行建模,通过半匹配求得负载差异最小的资源匹配结果,并且针对小规模和大规模问题分别设计了基于最优增广路径和基于遗传算法的最优半匹配算法。在资源匹配的基础上,本文给出了初步调度解的构造方法及其优化方法。4.研究了Om(P)|r,aN.I|Cmax问题制造期下界的计算方法。由于存在机器使用限制,无法通过简单的方法获得制造期的下界。因此,本文通过约束松弛将原问题转化为机器使用限制下可中断柔性开放车间调度问题(Om(P)|r,aN.I,pmtn|Cmax),Om(P)|r,aN.I,pmtn|Cmax易于解决,将它的最短制造期作为Om(P)|r,aN.I|Cmax问题制造期的下界。具体的解决方法是首先建立Om(P)|r,aN.I,pmtn|Cmax|司题的混合整数规划模型,在此基础上将模型中的约束条件转化为弧的容量约束,得到问题的网络流模型。然后,通过最大流算法求得它的制造期,以此作为Om(P)|r,aN.I|Cmax问题的制造期下界。5.针对Om(P)|r,aN.1|Cmax问题,给出了最坏情况界为2的稠密调度算法。Om(P)|r,aN1|Cmax问题允许机器在制造期内含有一个不可用时间窗,并且被中断工件在机器恢复可用后可以继续加工。文中将机器的不可用时间窗定义为虚拟工件,它的加工起止时间等于不可用时间窗的开始时间和结束时间。为了降低问题的难度,首先在不考虑虚拟工件的情况下进行资源匹配,进而通过分析虚拟工件与资源匹配制造期间的关系,得到三种模式关系。针对每种模式的特点,给出了考虑虚拟工件后的资源匹配调整方法。在此基础上,设计了Om(P)|r,aN.1|Cmax问题的稠密调度算法。在算法性能研究方面,本文从理论和算例试验两个方面分析了上述三种柔性开放车间调度算法的性能。在理论上,分析了调度算法的时间复杂度和最坏情况界,并通过随机产生的算例验证了算法的正确性,结果表明算法能够求得调度问题的有效解,并且制造期满足最坏情况界指标。更多还原

【Abstract】 Scheduling is the core content and key technology in production managerment. Proper and effective scheduling can help minimize makespan, waste of resources, and increase economic benefit. With the upgrading of market competition and complexity of production process, scheduling is playing an increasingly important role in the manufacturing industry.Flexible open shop scheduling problem (FOSSP) is one of the most well-known scheduling problems. Meanwhile, FOSSP is one of the most difficult combinatorial optimization problems. Mathematical modeling and approximation algorithms for FOSSP with preemptive constraint, non-preemptive constraint and machine availability constraint (Om(P)|pmtn,r1|Cmax、Om(P)||Cmax and Om(P)|r, aN.I|Cmax) were studied systemly in this thesis. Three approximation algorithms for the three FOSSP problems were proposed, which were based on network flow and semi-matching theory. And the performance parameters of the three algorithms were analysised, such as worse-case ratio and time complexityThe main contents are as following:1. Mathematical modeling methods of FOSSP were studied. Constraint conditions of Om(P)|pmtn, ri|Cmax、Om(P)||Cmax and Om(P)|r,aN.1|Cmax problems were analysis, which were represented by constraint functions. Then three mixed integer programming models with the objective of minimizing the makespan for Om(P)|pmtn, ri|Cmax、Om(P)||Cmax and Om(P)|r,aN |Cmax problems were established, which set a foundation for scheduling algorithm verification.2. A network flow based algorithm for Om(P)|pmtn, ri|Cmax problem was presented, which decomposed Om(P)|pmtn,ri|Cmax, problem into resource allocation and job sequencing two sub-problems. Firstly, the maximum flow model was developed to model the resource allocation and time constraints. and the maximum flow was the solution of the resource allocation, which made machine in full load condition. Moreover a new pre-flow push algorithm and optimization method for the maximum flow model were putforward, which used the least load first rule and the largest task first rule in active node selection. Based on the solution of machine allocation problem got by pre-flow push algorithm, the sequences of the tasks processed by each machine were determined by calculating the matrix of the processing times and decrementing set.3. Due to the complexity of Om(P)||Cmax problem, a dense scheduling algorithm was developed, which decomposed Om(P)||Cmax problem into resource matching and optimization two sub-problems. Only one operation of each job was completed in each resource matching, so m times of resource matching should be done for jobs set containing m operations. Initial solution was got by connecting resource matching results. Resource matching was modeled by a semi-matching on weighted bipartite graph, and two semi-matching algorithms were developed. For small scale scheduling problem, a balanced semi-matching algorithm based on augmenting path was presented, and a balanced semi-matching algorithm genetic algorithm was developed for large scale scheduling problem. Meanwhile, initial solution and scheduling optimization method was presented.4. The lower bound on makespan in Om(P)|r, aN.1|Cmax problem was studied. By relaxing the non-preemptive constraint, Om(P)|r, aN.1|Cmax problem can be converted into Om(P)|r, aN.1, pmtn |Cmax problem that can be solved easier, and the makespan of Om(P)|r, aN.1, pmtn|C problem can be served as the lower bound on makespan in Om(P)|r, aN.1|Cmax problem. The concrete procedure was that, firstly, the mixed integer programming model with the objective of minimizing the makespan for Om(P)|r, aN. 1,pmtn\Cmax problems was established, which was used as foundation to develope the maximum flow model for Om(P)|r, aN 1, pmtn|C, problem. Then, the makespan of Om(P)|r, aN.1, pmtn|Cmax problem can be got by maximum flow algorithm, which were the lower bound on makespan in Om(P)|r, aN. 1|Cmax problem.5. We developed a dense scheduling algorithm for Om(P)|r. aN.1|Cmax problem with a worst-case performance ratio less than 2. In Om(P)|r, aN.1|Cmax problem, each machine has a fixed and known unavailable period, and job interrupted by unavailable period can continue to be processed on the same machine after the machine has become available. In this thesis, the unavailable periods were treated as special jobs, which were called virtual jobs. In order to reduce the difficulty, resource matchings were done firstly without consideration of virtual job. Then, the relationship between makespan of resource matching and virtual job was analysis, and three modes were got. The method Based on the analysis, a dense algorithm for Om(P)|r, aN.1|Cmax problem were developed.The performances of the three algorithms developed in this paper were analysis from two aspects:firstly, worse case ratio and time complexity were analysis; then, the validity of the developed scheduling algorithms were illustrated by randomly generated examples.更多还原