供应链调度中的生产计划与分批策略研究

作     者：杨琴云 

作者单位：浙江工商大学 

学位级别：硕士

导师姓名：季敏

授予年度：2014年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：供应链调度 计算复杂性 NP-hard 完全多项式时间近似方案(FPTAS) 恶化效应 不可近似性 

摘      要：生产调度问题是一类经典的组合最优化问题,研究如何合理分配和调度有限资源以获得最大效益,在实际的生产中具有广泛的应用。高效的调度方案可以提高生产设备利用率、降低成本,增加企业的利润。供应链调度问题是生产调度问题的扩展,研究的是供应链的成员们(包括供应商、制造商、分销商和第三方物流等)在信息共享的基础上,为了达到缩短产品交货期,降低整条供应链运作成本的目标,实行联合(或协同)的调度,对生产制造领域有着重要的研究价值。 首先,本文对供应链调度问题的研究背景和意义进行了归纳总结并对其国内外研究现状做了详细介绍。 其次,对组合优化问题、调度问题、相关算法及计算复杂性进行了回顾,同时对于调度问题的求解思路以及本文所采用的主要算法做了简单介绍。 然后,研究了带有分批配送的供应链调度问题。我们先对原始问题作了复杂性分析,证明了该问题是强NTP-hard问题;对于配送批次有常数上界的情形,我们证明了是一般的NP-hard问题,并设计了完全多项式时间算法(FPTAS)。另外,我们还研究了三个多项式可解的子问题,对每个子问题设计了相应的多项式时间最优算法,并通过计算实例,验证了算法的有效性。 接着,研究了具有恶化效应的供应链调度问题。同样地,我们先对原始问题作了复杂性分析,证明了该问题是强NP-hard问题,并进一步证明了该问题不存在常数最坏情况界的多项式时间算法,除非P=NP;对于到达批次有常数上界的情形,我们对其做了复杂性分析,证明了该问题仍然是强NP-hard问题,并设计了FPTAS。 最后,我们对两个模型中设计的FPTAS通过数据试验,采用MATLAB软件对算法进行编程,对随机给定的实例找到了工件的最优批次数,每个批次工件的最优加工顺序,并求出了最优目标值,验证了FPTAS的有效性。