考虑机器使用成本的同类机调度问题

发布时间：2018-03-07 23:33

本文选题：生产调度　切入点：云制造　出处：《合肥工业大学》2017年硕士论文　论文类型：学位论文

【摘要】：本文基于云制造的背景,研究了考虑机器使用成本的同类机调度问题。制造业作为我国的支柱产业,自从改革开放以来,持续快速发展,与制造强国的差距很大。云制造是新兴信息技术与制造业相结合所产生的一种新型制造模式。实体制造资源通过云制造平台线上使用权交易,线下生产制造,能够实现分散异址制造资源的有效整合,从而实现制造资源与服务的开放协作、高度共享,以降低制造资源的浪费,对我国制造业具有至关重要的意义。云制造的实质是通过互联网实现制造资源的共享,因此在云制造环境下,生产调度必须考虑到机器使用成本。本文假定生产周期内机器的使用成本是固定的,研究了一类考虑机器使用成本的同类机调度问题,调度目标是在总成本预算范围内,最小化最大完工时间,以期达到生产成本与生产效率的平衡。首先我们假定了所有作业都是标准作业,即作业的加工时间相同,同时考虑了不可中断和可中断两种情形,我们通过对问题进行分析可知该问题是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算法来解决它。
[Abstract]:Based on the background of cloud manufacturing, this paper studies the scheduling problem of similar machines considering the cost of machine use. As a pillar industry of our country, manufacturing industry has been developing continuously and rapidly since the reform and opening up. Cloud manufacturing is a new manufacturing model produced by the combination of emerging information technology and manufacturing. Physical manufacturing resources are traded online through cloud manufacturing platforms for offline manufacturing. It can realize the effective integration of decentralized manufacturing resources, realize the open cooperation between manufacturing resources and services, and share highly, so as to reduce the waste of manufacturing resources. The essence of cloud manufacturing is to share manufacturing resources through the Internet, so in the cloud manufacturing environment, In this paper, the machine cost is assumed to be fixed in the production cycle. This paper studies a class of machine scheduling problems considering the machine usage cost. The scheduling goal is within the total cost budget. Minimize the maximum completion time in order to achieve a balance between production costs and production efficiency. First, we assume that all jobs are standard, that is, the same processing time, taking into account both non-interruptible and interruptible situations. By analyzing the problem, we know that the problem is NP-hard. For the non-interruptible case, we propose a heuristic algorithm H1 based on the ECT rule, and prove that its maximum error bound is 2 [1.1 / h-1]. We propose a heuristic H _ 2 algorithm, and prove that the maximum error bound of H _ 2 algorithm is 1 / 1 / h ~ (-1), where h is the machine that is skipped in the selection machine for the first time. Finally, the validity of these two algorithms is proved by a large number of programming data experiments. In this paper, we study the scheduling problem of the same kind of machine considering the cost of machine use when the job is a common job (that is, the processing time of a job is different). Our objective function is also within the total cost budget. Minimization makespan.Through analyzing the problem, we know that the problem is NP-hard. We also consider the non-interruptible case and the interruptible case. For the non-interruptible case, we based on the improvement of the classical LPT algorithm. A MLPT algorithm is proposed. It is theoretically proved that the maximum error bound of the algorithm is 2 [1 / 1 / h], in which h is the machine that is skipped for the first time in the selection machine. Finally, the validity of the algorithm is proved by a large number of programming data experiments. On the basis of Level algorithm, we propose a heuristic algorithm H 3 algorithm to solve it.
【学位授予单位】：合肥工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【相似文献】