论文部分内容阅读
本文基于云制造的背景,研究了考虑机器使用成本的同类机调度问题。制造业作为我国的支柱产业,自从改革开放以来,持续快速发展,与制造强国的差距很大。云制造是新兴信息技术与制造业相结合所产生的一种新型制造模式。实体制造资源通过云制造平台线上使用权交易,线下生产制造,能够实现分散异址制造资源的有效整合,从而实现制造资源与服务的开放协作、高度共享,以降低制造资源的浪费,对我国制造业具有至关重要的意义。云制造的实质是通过互联网实现制造资源的共享,因此在云制造环境下,生产调度必须考虑到机器使用成本。 本文假定生产周期内机器的使用成本是固定的,研究了一类考虑机器使用成本的同类机调度问题,调度目标是在总成本预算范围内,最小化最大完工时间,以期达到生产成本与生产效率的平衡。首先我们假定了所有作业都是标准作业,即作业的加工时间相同,同时考虑了不可中断和可中断两种情形,我们通过对问题进行分析可知该问题是NP-hard的,针对不可中断情形,我们在ECT规则基础上提出了启发式算法H1算法,并证明了其最大误差界为2[1+1/(h-1)];针对可中断情形,我们提出了启发式算法H2算法,并证明了其最大误差界为1+1/(h-1),其中,h是在选机器中第一次跳过的机器。最后通过大量的编程数据实验表明了这两个算法的有效性。 接着,本文研究了作业为普通作业(即作业的加工时间不同)时的考虑机器使用成本的同类机调度问题。我们的目标函数同样是在总成本预算范围内,最小化makespan。通过对问题进行分析可知该问题是NP-hard的。我们同时考虑了不可中断情形和可中断情形,针对不可中断情形,基于对经典的LPT算法的改进,提出了一个MLPT算法。理论证明了该算法的最大误差界是2[1+1/(h-1)],其中,h是在选机器中第一次跳过的机器。最后也通过大量的编程数据实验表明了该算法的有效性。针对可中断情形,我们在Level算法的基础上提出了启发式算法H3算法来解决它。