具有恶化效应和切换时间的生产调度问题研究-机械工程专业毕业论文.docxVIP

A A Dissertation Submitted to Guangdong University of Technology for the Degree of Master of Science IIII l U U Ill U I II U III Master of Engineering Science Y30421 07 Research on Job—shop Scheduling with Deterioration Effect and Setup Time By He Ning Supervised by Prof．Wu Naiqi May 2016 School of Electromechanical Engineering Guangdong University ofTechnology Guangzhou,Guangdong E R．China，5 1 0006 万方数据 摘要摘要 摘要 摘要 制造业一直以来都是国家的命脉，占据国民经济很大的份额。伴随着市场环境不断 的变化，如何制定有效的调度方案，以降低产品成本，提高产品质量和整个生产系统 的生产效率，将是企业在激烈的竞争中获得优势的法宝。因此，车间调度问题受到广 大学者的研究。这一问题具有建模复杂性、计算复杂性、多约束、多目标等特点，是 典型的NP．难组合优化问题的范畴。车间调度问题根据其生产系统的复杂度可以分为单 机调度和多机调度，它们源于不同的生产制造车间，同时可以作为实际生产线的抽象 模型，很适合于多品种小批量生产背景的制造企业。而在实际的生产加工过程中，工 件的加工时间常伴随着工件的开始加工时间的延长而延长，这类现象称为恶化效应。 本文通过假设恶化效应是时间的线性函数，研究了具有恶化效应和投放时间约束的单 机成组调度问题和具有恶化效应和切换时间的两台机流水车间调度问题。 文中首先对研究背景、意义以及目前研究现状进行了详细的介绍，同时提出了本文 的研究对象，定义了车间调度问题，并详细地介绍了调度问题中常见的约束以及求解 此类调度问题的方法。 针对具有恶化效应和投放时间约束的单机成组调度问题，文中通过分析此调度问题 的特性，给出了两个定理，同时对定理给予了证明。基于以上两个定理，文中提出了 该问题可由多项式算法求解，并给出了具体多项式算法。最后给出了实例，验证了所 提出的算法的有效性。 针对具有恶化效应和切换时间的两台机流水车间调度问题，文中通过分析此调度问 题的特性，建立了混合整数规划数学模型，针对MIP不能解决大规模问题的缺点，文中 提出了启发式变邻域有哪些信誉好的足球投注网站算法求解。变邻域有哪些信誉好的足球投注网站算法的核心在于获取初始解和邻域结 构集，因此，文中设计了贪婪算法用于获取初始解，同时设计了四种邻域结构操作， 用于改变邻域结构。为了更好的评价变邻域有哪些信誉好的足球投注网站算法的优劣，文中给出了两个求解下 界的计算方法。最后给出随机数据实验分析了本文提出方法的有效性。 关键词：车间调度，恶化效应，变邻域有哪些信誉好的足球投注网站算法，MIP，算法复杂性 万方数据 广东工业大学硕士学位论文Ab 广东工业大学硕士学位论文 Ab stract The rmnufacturing industry is always the lifebbod of a country,a share of mtioml economy greatly．In order to reduce product cost，improve product quality and productivity, effective scheduling strategy plays an in∞ortant part in the development of companies such that they Call survives in the fierce market competition．Therefore，shop scheduling problem is studied by rmny researchers．Due to the complexity of modeling,computatioml complexity, rmny constraints and objectives，such scheduling problem is a typical NP-hard problem such that it is very difficult to so lve it．Job—shop scheduling problem can be divided into single machine scheduling and multi-machine scheduling．In practice，m