开题报告.pptx

带安装时间单机调度问题的禁忌算法,点击添加标题,研究方法及预计要遇到的难题,研究预计达到的效果,主要内容,研究背景,研究的意义及价值,研究现状及发展趋势,带安装时间单机调度问题的禁忌算法,单机调度的含义与特点,研究背景,禁忌算法的特点及优势,什么是带安装时间单机调度问题,研究意义：单机排序问题对于有效地利用资源，提高生产效率，具有十分重要的指导意义,特点：1.是最简单的一类调度问题，也是最重要的调度问题之一；2.单机调度问题大量存在于现实生活中，具有广泛的实际背景。,一：单机调度的含义与特点,定义：将若干工件（job）在一个机器上进行加工，合理安排机器和工件，以使目标函数最优的过程。,算法的优点：搜索时能够跳出局部最优解，从而增强获得更好的全局最优解的概率，所以TS算法是一种局部搜索能力很强的全局迭代寻优算法。,特点：TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。,二：禁忌算法的特点及优势,简介：禁忌搜索（简称TS）它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。,三：什么是带安装时间单机调度问题,1.该问题的描述：可看成企业在一台机器上加工不同的零件（作业）调度员按照生产零件规格的不同划分成不同的组机器在加工同一个组内的作业时，不需要安装时间，但当机器从加工一个组的作业切换到生产另外一个组的作业时，需要相应的安装时间,2.该问题的现实矛盾：当我们希望提高机器利用率时，我们倾向于把同一个组的作业连续加工，以减少安装时间，但这样造成同组占用时间较长，往往会导致其他组内的作业拖期；当我们以交货期为准则来进行调度时，我们倾向于先调度交货期紧的作业，但这样会导致更多的安装次数和安装时间，降低了机器利用率，也最终会导致作业拖期。,在该类问题上，已有不少理论研究，主要集中在精确算法(动态规划算法和分枝定界算法),研究现状及发展趋势,精确算法(包括上述动态规划法和分枝定界法)的算法非常复杂，无法求解实际问题。,目前研究带序相关安装时间的调度问题(类似于该研究的问题)还不充分，有待进一步研究。,研究的意义及价值,带安装时间单机调度问题在实际企业中有广泛的应用背景，例如钢铁的线材加工行业和染色行业（在不同作业组切换时存在着序相关的安装时间)。因此，研究这类问题具有很高的理论价值和实际应用价值。,研究方法及预计要解决的难题,研究方法,预计难题,建立合理的问题模型。,研究方法,设计两种算法，借助VC+等平台编辑算法并举例计算。,同一平台上比较不同算法计算完成所需时间，进行分析并得出结论。,理解并掌握禁忌搜索算法的基本流程,预计难题,设计两种能正确运行的禁忌搜索流程,需要建立合理的计算程序来完成计算,研究预计达到的效果,1.通过举例计算出两种算法所用时间。,2.能够通过两种算法的运算耗时比较出它们的优劣。,3.以论文的形式将该研究呈现出来，并能够对实际生产的过程中提供帮助。,参考文献,1 排序引论/唐恒永，赵传立编著.北京：科学出版社，2002,2 现代优化计算方法/邢文训，谢金星编著.2版。北京：清华大学出版社，2005.9,6 On scheduling with ready times and due dates to minimize maximum lateness,3 求解带组换装时间单机调度问题的禁忌搜索算法 刘振刚，王道平，金锋 运筹学学报，2008,12(4),7 A Tabu Search Algorithm for Single Machine Scheduling with Release Times,Due Dates,andSequence-Dependent Set-up Times,4 运筹学教材编写组，运筹学（修订版）.北京：清华大学出版社，1990,5严颖，成世学，程凯.运筹学随机模型.北京：中国人民大学出版社，1995,感谢,