基于分枝定界方法的人造卫星生产调度研究

《基于分枝定界方法的人造卫星生产调度研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据东北大学硕士学位论文第1章绪论161课题研究背景第1章绪论生产调度所研究的问题就是在有限的资源和时间约束下，制定出一套生产调度策略，使得某个或者多个目标达到最好。调度问题广泛存在于现实世界中，是一类经典运筹学问题，是组合优化中的一个重要分支。它最初应用于机器制造业，现在逐渐发展为系统科学、运筹学、管理科学、控制科学和计算机科学等多个学科领域的交叉学科，广泛应用于工程技术和经济管理的各个领域。科学技术的迅速发展，促使人们对产品的个性化要求越来越高，当今这种变化迅速的市场环境对企业生产提出了越来越高的要求，不但要准时还要有柔性

2、空间。影响生产过程的因素有很多，包括客户要求多变、资源缺乏、突发事件及负荷不均衡等不确定因素干扰，生产调度成为当前机器制造工程领域研究的热点之一。传统大规模生产模式越来越不能满足竞争要求，多品种小批量生产越来越成为主流，特别是某些特殊行业，其生产方式几乎全部为多品种小批量。在多品种小批量的生产调度中，由于制造系统的随机性，系统的瓶颈随着不同的产品或任务组合而漂移，变得难以确定。航天领域的生产系统明显是多品种小批量的生产模式，自人造卫星问世以来，它便在通信广播、对地观察、导航定位、深空探测、载人航天、军事等方面发挥了重大的、无可替代

3、的作用。我国也相当重视卫星的发展，卫星发射技术己处于世界前列，但由于人造卫星种类多，而每种类型的卫星生产量低，使得人造卫星生产研究成为学术界具有挑战性的课题，同样，航天零件的生产企业也面临着同样的问题。航天制造企业如果要实现生产过程合理化、自动化、集成化，采用有效的调度算法和优化技术是其提高生产效益与市场竞争力的关键。近年来，人们对车间调度问题进行了广泛的研究，其范围涉及流水车间调度问题、作业车间调度问题和开放车间调度问题等。有关资料表明：约有25％的生产制造系统、组装线和信息服务设施可简化为流水车间模型，且很多流水车间调度问题是

4、NP难问题。因此，流水车间调度问题成为研究最广泛的生产调度问题之一。本文以航天零件生产为背景，研究了几种典型流水车间调度问题模型；针对多品种小批量的生产模式，设计了有效的分枝定界算法进行最有求解，在一定程度上为相关的调度问题提供了研究思路和理论方法。·1-万方数据东北大学硕士学位论文第1章绪论1．2生产调度问题概述1．2．1调度问题的定义与描述调度(scheduling)研究的问题是将稀缺资源(resource)分配给在一定时间内的不同任务(task)。它是一个决策过程，在大多数制造和生产系统及信息处理环境中扮演着重要的角色。同时

5、，调度也是一门应用科学，它在物流管理、交通运输、工业生产等方面都有着深刻的实际背景和广阔的应用前景。机器制造业中的调度问题可称为生产调度问题，生产调度问题可简单描述为：对于某项可以分解的工作(如钢铁加工等)，通常把资源称为机器-(machine)，把任务称为工件(job)，在一定的约束条件下(如工艺次序约束、资源约束、交货期约束等)，为了使一个或多个目标达到最优，对工件和机器按时间进行分配和安排次序。这里的机器和工件可以延伸为广泛的实际对象。生产调度问题主要包含三个因素：约束条件、性能指标和调度方案。其中约束条件指的是在决策过程中

6、的各种约束限制，比如人力物力成本、工件加工次序、材料运输时间、设备故障等；性能指标是评价调度方案优劣的依据，可以是成本最低、费用最小、生产周期最短、提前拖期最小、设备利用率最高、客户满意度最高等；调度方案是需要解决的生产调度问题的解。目标就是要找到一个合理的调度方案，它可是一组实数，也可以是一个排列。在调度问题中，一般包含一定的机器数和工件数，这里分别设为m和n。本文中，指标歹指一个工件，而指标f指一台机器。如果一个工件需要许多加工步骤，则数对(f√)指的是工件．，在机器f上的加工步骤。将本文中主要涉及的与工件．，相关的数据定义如

7、下：(1)加工时间(processingtime)p(i，，)：指工件歹在机器f上加工所需的(非负的)时间。(2)释放时间(releasedate)rj：也称为到达时问(arrivaltime)或准备时间(readytime)等，都是指工件，到达系统的时间，是该工件可以开始加工的最早时间，若所有的工件都是同时就绪，则可认为o=o，(，=1，．．．，，2)。(3)交货期(duedate)d，：也称为工期，表示客户对工件／限定的完工时间。(4)运送时间(deliverytime)dj：表示工件歹加工完成后，配送到目的地的时间。(5)完

8、工时间(completiontime)C(i，J)：指工件，在机器f上加工完成的时刻，流水车间调度中，在最后一台机器上的完工时间表示为C(m，J)，另外也可表示为C，。(6)送达时间D，：指工件，在机器上加工完成的时间与配送到目的地的时间之和。．’