● 摘要
摘 要
自从上世纪50年代以来，生产调度就成为了运作管理领域中一个重要的研究和应用问题。调度的主要目标，是合理分配资源确定作业加工顺序，以求高效完成各项作业。在调度问题中，“工作”表示作业，机器代表资源。生产调度是一个NP-难问题，非常难以求解。这也是近几十年来该问题被广泛研究的原因之一。调度问题非常重要，它是一个有力的工具，可用来解决组织、生产方面的复杂管理问题，减少运作成本、提高客户服务水平、优化资源使用，提高在线交付率，减少库存和提前期。
人们最初使用精确算法求解调度问题。但是，由于调度问题一般是NP-难的（随着问题规模增长，需要的计算时间急剧增加），研究人员便转向使用元启发式算法和混合启发式算法求解（如粒子群优化、蚁群优化、模拟退火、禁忌搜索、遗传算法、神经网络和免疫算法等）。
本文考虑批量调度问题。其中假设机器能力有限，需要完成的工作批量可以变化，所有在机器上处理的工作不能超过机器的能力。假设机器m在其处理能力范围内，可对某批产品并行处理，那么本批次产品的总的处理时间就是其中消耗时间最长的工作的处理时间。本文进一步考虑生产准备时间，建立了最小化生产总时间（make-span）的生产调度模型。模型包括三类：单机调度、流水线调度和车间调度。由于调度模型的复杂性，精确算法难以求解，因此本文分别提出了两个遗传算法：JBSPGA（作业车间批量调度问题的遗传算法）和FBSPGA（流水车间批量调度问题的遗传算法）求解所提出的三类调度问题。
最后，本文通过算例说明了模型的建立和算法的运用，并通过标准算例研究了算法的有效性和参数对算法性能的影响。
关键词：调度，作业车间，流水车间，遗传算法