【摘 要】
：
调度问题是组合优化和运筹学领域中最为经典的问题之一,已有几十年的研究历史。受现实生活中生产环境和实际应用的影响,在对调度理论的研究过程中提出了许多模型,这些模型吸引了许多学者对其进行研究。本文主要研究了多台无关机上最小化误工损失的调度问题,在该机器环境中每个任务都具有独立的交付期,每一台机器对于同一任务具有不同的处理速度,且执行过程中不允许抢占。此外,本文的研究目标是减少误工损失,而不是经典的完工
论文部分内容阅读
调度问题是组合优化和运筹学领域中最为经典的问题之一,已有几十年的研究历史。受现实生活中生产环境和实际应用的影响,在对调度理论的研究过程中提出了许多模型,这些模型吸引了许多学者对其进行研究。本文主要研究了多台无关机上最小化误工损失的调度问题,在该机器环境中每个任务都具有独立的交付期,每一台机器对于同一任务具有不同的处理速度,且执行过程中不允许抢占。此外,本文的研究目标是减少误工损失,而不是经典的完工时间指标。对于具有任意交付期的通用模型Rm|d=dj|Y,本文建立了一个混合整数规划模型,并调用Gurobi优化工具对该模型进行求解。此外,为了求解该问题,本文还提出了带有截断规则、上界和下界技术的PDP算法和B&B算法。在B&B算法中,提出了DPRm算法作为新的下界,DPRm算法扩展了前人提出的动态规划算法,用以解决系统内所有任务的交付期都相同的简化模型Rm|d=d’|Y,不仅扩大了动态规划算法的适用性,也由此证明了Rm|d=d’|Y问题的弱NP性。本文设计了不同的实验场景来比较算法的性能,实验主要分为小规模实例测试和大规模实例测试。在小规模实例测试中,分别使用PDP算法、B&B算法和调用Gurobi求解器对Rm|d=dj|Y问题的混合整数模型进行求解,并对这三种方法进行了对比实验,通过实验验证了混合整数规划模型的正确性和有效性。从实验结果可以看出,本文所提出的PDP算法和B&B算法比使用Gurobi求解的混合整数规划模型的运行速度更快。在大规模实例测试中,对PDP算法、B&B算法和TS算法的性能进行了比较和分析。从实验结果可以看出,虽然TS算法的运行速度较快,但与最优解之间比值的平均值为114.53%。而PDP算法和B&B算法虽然都为精确算法,在任务数量和机器数量都较小的情况下,PDP算法的运行速度优于B&B算法,当任务和机器的数量都增大时,B&B算法又表现出比PDP算法更为优异的性能。
其他文献
湿法脱硫后的湿烟气向环境中排放时会产生白烟,白烟污染环境,加剧雾霾的形成,因此湿烟气排放产生白烟的问题亟待解决。近年来国内各地对白烟现象提出了控制要求,这对于环境保护有着重要的意义。因此研究烟气消白有着重要的现实意义。本文针对湿烟气排放产生白烟现象,采用汽水扩散湿烟气消白技术消除视觉白烟,确定工艺方案和控制方案,依据控制方案进行控制系统设计,确保消除视觉白烟。对汽水扩散湿烟气消白进行了理论研究。通
随着全世界范围内的汽车保有量日益增长,由此造成了城市交通不畅、汽油紧缺和交通安全等问题的出现,其中交通安全事故最为普遍。无人驾驶汽车的智能驾驶技术不仅仅在一定程度上提高了车辆的主动安全性,而且还缓解了高峰时期的交通压力,因此具有重要的实际应用意义。准确有效的轨迹跟踪控制是无人驾驶的关键所在,并且对无人驾驶汽车的量产与使用具有积极重要的现实意义。本文基于中华V3无人驾驶汽车作为该试验平台,基于该平台
不确定非线性系统的研究在控制范畴一直是学者们的关注焦点,随着技术的发展,实际被控系统不再单一,为适应工程需要,许多复杂的实际系统总是期望收敛时间最短,或系统某一性能指标为最优。因此,相对于研究时间趋于无穷或不满足性能指标的控制问题,致力于研究有限时间及优化控制通常拥有更好的理论与工程应用前景。本文在模糊或神经网络智能控制大框架下,结合三大基本控制理论（有限时间控制,自适应控制和优化控制）,针对几类
当汽车在人们的生活中普遍使用,汽车不再是简单的代步工具,其平顺性逐渐成为关注的焦点。汽车行驶时与路面直接接触,悬架振动的强度与路面状况有直接关系。因此在车辆行驶过程中,对路面的等级进行在线辨识,并将辨识到的路面情况与悬架控制系统相结合,实现悬架系统自动调节参数的功能,提升车辆平顺性。本文基于车辆动力学响应的反向分析法辨识路面信息,得到路面等级信息后,设计显式模型预测控制器对可控悬架控制,从而使车辆
在未来的几十年内汽车会慢慢的从目前辅助驾驶过渡到智能无人驾驶,而目前取得一定阶段性研究生成果的则是智能驾驶领域的高级辅助驾驶系统,而ACC又是发展时间较早研发时间较长取得研发成果显著的并且能量产高级辅助驾驶系统之一,ACC系统通过系统主动控制车辆制动系统和驱动系统可以有效的减轻驾驶员的操作负担,并且减少道路交通事故率,改善道路利用率的问题,还可以有效的提高汽车的舒适性以及燃油经济性。所以对自适应巡
当今社会随着科技的不断进步,汽车制造技术迅速发展,但随着传统燃油车数量的剧增,能源逐渐短缺,人类生存环境恶化,使得纯电动汽车迅速崛起。分布式驱动电动汽车属于纯电动汽车,该类车型的制动系统并不只是单纯的使用传统的液压制动,而是将电机制动与液压制动进行复合使用,既能提升车辆制动过程中的性能,又能进行能量回收,提升车辆续驶里程。分布式驱动电动汽车复合制动系统研究的重点在于制动力合理分配与控制策略有效可行
众所周知,许多实际工程系统中都存在未建模动态、时滞、未知控制增益等现象,这些现象成为导致被控系统不稳定的一个重要因素。随着科技发展的脚步迈的越来越快,许多工业领域对控制系统的控制品质要求的越来越高,它们不只是要求被控系统是稳定的,还希望被控系统能够具有一定的鲁棒性,这使被控系统的理论研究更有实际意义。所以,近年来控制领域在研究系统稳定性的基础上逐渐加强对非线性系统的鲁棒控制的探索。本文以模糊自适应
长时间的连续驾驶会导致驾驶员的生理性疲劳与注意力分散,使其对车辆的控制能力降低,发展智能车自动驾驶技术是解决该问题的技术方向之一,并已成为汽车领域的研究热点。对于自动驾驶而言,在实现循迹、避障等常规驾驶动作外,舒适性是自动驾驶控制品质的直接体现之一,是影响乘员主观感受的重要因素。项目依托国家自然科学基金项目（51875302）和国家自然科学基金项目（51675257）,对智能车辆转向行为下乘员舒适
约束作为制约系统性能的重要因素之一,广泛存在于实际系统中。因此,针对状态或者输出约束的研究在非线性控制领域显得尤为重要。结合障碍李雅普诺夫函数和反步法,针对非线性系统,进行了如下四个方面的研究工作:（1）针对一类具有时变全状态约束的严格反馈非线性系统,提出了一种自适应死区补偿控制方法。首先,构造了障碍李雅普诺夫函数和反步法来保证时变全状态约束不违反约束界并且使系统输出尽可能接近目标轨迹。其次,在反
近年来,随着社会经济的不断发展,能源枯竭以及能源浪费问题已经得到越来越多人的关注。大量使用传统能源产生有害物质,导致全球变暖、酸雨、雾霾等严重的生态环境问题,大力推动和发展以太阳能为代表的可再生能源具有广阔的前景。从建筑节能角度出发,将太阳能应用到寒冷地区农村居住建筑供暖系统中,可以减少传统能源使用,改善农村建筑室内环境。本文以寒冷地区典型的农村单体式建筑为研究对象,对带有相变蓄热的太阳能供暖系统