论文部分内容阅读
本文研究一类加工时间连续可控条件下的双机床加工中心调度问题。该问题突破了经典调度研究中任务加工时间固定且已知的假设,引入了可通过额外分配和消耗一定资源(如人力、电力、燃气和资金预算等)而加以压缩和控制的任务加工时间,从而更好地对现实生产环境中的加工中心加工模式进行建模和研究。 在引入可控任务加工时间的基础上,本文研究如何合理有效地向每项任务分配资源以压缩其加工时间,以及如何合理安排任务加工的机床分配和加工顺序以提高机床工作效率,从而在确保所有任务完成时间不超过交货期的前提下,最小化额外消耗的总资源量,继而有效降低生产成本,提升企业核心竞争力。本文假设任务加工时间与资源消耗量之间可由一个非升凸函数加以描述,由于资源消耗与加工时间连续可变,因此该问题是一个非线性混合优化问题,且其计算复杂度为NP完全。针对这一问题,本文研究并得出相应的调度优化算法,用于在可接受的计算时间内为问题构造令人满意的近优解。该算法包括两个相互独立又相互配合的子算法:资源分配算法用于在任务加工顺序已确定的假设下,最优地分配资源到各个任务,从而使资源消耗量最小;加工顺序搜索算法用于找出最优或近优的任务加工顺序。 本文基于拉格朗日松弛及最短网络路径方法为资源分配问题构造出多项式时间解,基于禁忌搜索算法为任务加工序列问题构造出近优解。大规模数值计算试验表明,本文所完成研究能够在可接受计算时间内,为中小规模加工时间可控的双机床加工中心调度问题构造出最优解或近优解。