论文摘要
近年来,随着科学技术的不断进步以及生产力的飞速发展,消费者的需求越来越多样化与个性化,要求制造商能在承诺交货期前交货。而制造商的配送往往外包给第三方物流公司,订单的生产必须在配送之前完成,订单生产无拖期。在满足消费者交货期以及物流公司配送决策的前提下科学又合理的进行车间调度,降低生产总成本,是制造商面临的一个非常现实的问题。本文首先介绍了无拖期车间调度问题的研究背景与研究意义,接着论文主要研究了无拖期条件下,车间调度中最常见的两种类型——流水车间调度问题与作业车间调度问题。对于小规模的两台机器的流水车间无拖期调度问题,提出拉格朗日松弛算法把加工路线的约束松弛到目标函数中,求得问题的下界,然后提出一种启发式算法把下界可行化,并使用局部搜索算法对启发式解进行进一步的优化,设计了分支定界算法求其最优解,仿真实验表明,分支定界算法可求出小规模问题的最优解,启发式算法则可得到较大规模问题的高度次优解。为了使研究的问题更具有普遍性与代表性,论文研究了多机作业车间无拖期调度模型,设计了求解此问题的模拟退火算法,通过实验获得该算法的参数设置,之后,使用带记忆的回火退火算法与并行退火算法对基本的模拟退火算法进行了改进,通过随机产生的算例,证明了各种算法的有效性与可行性,得出了各自不同的适用范围。