【作者】 张强；

【导师】 任涛； 于鹏；

【作者基本信息】 东北大学 ， 软件工程（专业学位）， 2016， 硕士

【摘要】 医疗检查过程中的部分检查过程可以抽象为开放作业调度模型,因此研究开放作业模型有助于解决医疗检查过程中的调度问题。在开放作业调度问题中,每个工件经过机器的顺序是任意的,在任何时刻,每台机器最多加工一个工件,每个工件最多只能被一台机器加工。一旦工件开始加工,加工过程不能中断直到其加工完为止,目标是找到一个可行调度使得某个调度准则最小。开放作业调度问题广泛应用于工程技术和质量检查等各个领域。本文主要对开放作业调度模型中的两个问题进行了研究,分别设计了分枝定界算法和差分进化算法,求得问题的最优解或近似最优解。最后通过数值实验仿真验证了算法的有效性。具体内容概括如下:(1)针对带有释放时间的极小化最大完工时间问题,设计了基于直线编码方式的分支定界算法和基于析取图模型的分支定界算法。在基于直线编码方式的分支定界算法中,给出了分支策略和剪枝过程以及上界和下界的设计。然后设计相应的数值仿真实验用来与IBM公司的CPLEX软件比较,最后对实验结果进行分析,得出结论。在基于析取图模型的分支定界算法中,首先证明了分支策略的可行性,然后给出了分支策略和剪枝过程以及上下界的设计。然后设计相应的数值仿真实验用来与IBM公司的CPLEX软件比较,最后对实验结果进行分析,得出结论。(2)研究带有释放时间的开放作业极小化最大延误问题。针对中小规模问题,设计了离散差分进化算法,并给出了变异、交叉和选择的过程,并提出了改进策略,最后设计相应的数值仿真实验,将差分进化算法得到的目标函数值与初始解的目标函数值进行对比,然后对实验结果进行分析,得出结论。针对大规模问题,设计了 DS-EDD启发式算法,给出了算法的具体流程,并给出了相应的下界作为对比,然后设计相应的数值仿真实验来验证算法的性能,通过对实验结果进行分析并得出结论。更多还原

【Abstract】 Many kinds of medical inspection process can be abstracted into open shop scheduling model,therefore,researching.For an open shop scheduling problem,each job can be processed by machines in any order.Each machine can process at most one job at one time and each job can be processed by at most one machine at one time.The processing procedure can’t be interrupted until it is completed.The objective of open shop scheduling problem is to find a schedule minimizing one or some criterions.Open shop scheduling problems are widely applied to engineering technology and quality inspection and etc.Two kinds of criterions are considered in this paper,and branch&bound algorithm is designed to obtain the optimal solution for makespan problem,while differential evolution algorithm is applied to maximum lateness problem to obtain a near-optimal solution.Numerical simulation experiments are executed to demonstrate the effectiveness of these algorithms.The contents are summarized as follows:For minimizing makespan problem with release dates,branch&bound algorithms based on line coding and disjunctive graph model are designed.For the branch&bound algorithm based on line coding,branch strategy and lower bound and upper bound are presented.To demonstrate the effectiveness,the algorithm is compared with CPLEX of IBM by numerical simulation experiments.The branch strategy,lower bound and upper bound are presented for the branch&bound algorithm based on disjunctive graph model,and the feasibility of branch strategy is proved.The numerical simulation experiments comparing with CPLEX is executed too.This thesis researches the open shop scheduling problem to minimize the maximum lateness.For small and medium scale problem,the discrete differential evolution algorithm is designed.An improvement strategy is designed for this algorithm,then the numerical simulation experiments are executed.For large scale problem,DS-EDD heuristic algorithm is designed.The flow of the algorithm is presented and a lower bound is designed to compare with the heuristic algorithm.Then the performance of the algorithm is shown by numerical simulation experiments.更多还原