QQ客服 官方微博 反馈留言

题名	成组加工生产系统中若干调度问题的研究
作者	王书锋
学位类别	工学博士
答辩日期	2002-05-01
授予单位	中国科学院研究生院
授予地点	中国科学院自动化研究所
导师	邹益仁
关键词	成组加工 订单排产 机器调整 主 准时制 最大拖期 遗传算法 禁忌搜索算法 混合优化策略 灵敏度分析 batch processing order planning machine setup major and minor setup time just-in-time maximum lateness genetic algorithm(GA) tab 从调整时间
学位专业	控制理论与控制工程
中文摘要	本文以钢铁工业成组加工生产系统中的生产计划与调度问题为研究背景，针 对其中涉及的一些理论问题和几个典型的调度问题，展开了优化特性和一系列求 解方法的研究。进行此类问题的研究不仅符合调度问题的研究发展趋势，同时具 有重要的理论和实际应用意义。 论文的主要内容和创新之处如下： 1．订单优化排产算法的研究首先，对单机准时制生产模式下的订单提前/拖 期惩罚问题，证明问题是NP—hard的，将Peng等人的有关求解单机提前/拖期调 度问题的一些结果进行扩展，证明了在订单优化排产中临近批组的优化特性。据 此提出了基于优化特性的过滤束搜索算法，并分析算法在最坏情况下的计算复杂 性；其次，提出并证明了有公共交货期的订单最大绝对延期问题的最优化算法， 其计算复杂性为O（blog6）；最后，对订单最大延迟问题，分别提出0—1混合整数 规划和约束规划两种求解模型并进行了验算，对中小规模问题取得一些有意义的 结果，表明约束规划模型得到的最优解更有效。 2．有主从多级调整时间的成组加工问题由于实际生产中存在批量大小的有 效性同满足客户交货期的协调问题，提出以工件最大延迟为优化目标的有主从多 级调整时间的成组加工问题，基于复合工件的概念推导出部件类调整交货期和大 类调整交货期的计算式。在证明组技术假设下优化排序的必要条件下，设计了基 于优化特性的禁忌搜索算法。 3．基于遗传算法的混合优化策略的研究对遗传算法的收敛性进行深入的分 析，提出改进的编码技术及改进的交叉和变异算子可以不同程度提高遗传算法的 收敛性。由于禁忌搜索和遗传算法各自的局限性，针对一类有批量和容量限制的 多产品调度问题，提出基于遗传算法和禁忌搜索的混合优化算法；算法采用实数 编码方式，利用禁忌搜索产生初始种群，并采用改进的自适应变异算子提高算法 的并行搜索能力，对算法进行了仿真。 4．不确定加工时间条件下的调度算法和灵敏度分析讨论线性规划的灵敏度 分析及调度问题灵敏度分析的基本概念，在占一摄动处理时间下，给出j司题 1//∑Ci在任意调度算法和SPT排序规则下灵敏度保障的界值。在有学习功能的 处理时间的情况下，分别提出单机提前、拖期和完工时间罚值问题和平均流程时 间问题的最优化算法，并设计仿真算法以验证最优化算法的结果。
英文摘要	This research, which is conducted in the area of production planning and scheduling problems of batch processing in Iron & Steel industry, focuses on the optimal properties and solution procedures with regard to some particular theoretical problems and a few typical scheduling problems. It is believed that such kind of research is theoretically and practically significant, and in conformity with the trend of the research and development in this area. Main works and contributions included in this dissertation are: 1. Study of the algorithms for the optimal order planning. In the first place, the NP- hardness of the single-machine order planning to minimize the earliness and tardiness under the just-in-time production strategy is proved. Afterwards the optimal properties of adjacent groups in optimal order planning are discussed by extending Peng's research result concerning the single-machine earliness and tardiness problems. And then an optimal property-based filtered beam search algorithm is proposed with the computational complexity of the algorithm investigated under the worst case analysis. Second, the optimal solution to the problem of the maximum absolute lateness of orders with common due date is proposed and testified. The computational complexity of such optimal algorithm is O(b log b). Finally, two models of minimizing the order's maximum lateness, namely the 0-1 mixed integer-programming model and the constraint programming model, are proposed. The simulation results indicate higher efficiency of the optimal solution of constraint programming. Some good results have been obtained from their application to middle-small size problems. 2. Batch processing scheduling problem with major and minor setup times. In the real manufacturing process, there usually exists a trade-off between achieving the batch size efficiency and meeting customers' due date. In view of this, batch processing problem with major and minor setup times to minimize the job's maximum lateness is brought under detailed consideration. By applying the concept of composite job, some formulae for the due date of the composite job and the family due date are presented. A set of necessary conditions for group sequencing under the group assumption has been identified. In the end, a property-based tabu search algorithm is proposed and simulated. 3. Research on the GA-based hybrid optimal strategy. With a profound analysis of the genetic algorithm's convergence, the research discusses the important role of improved coding technology and improved crossing and mutation operators in promoting the convergence of the GA. On account of limitations of the GA and TS, a hybrid algorithm incorporating the two heuristics is recommended in dealing with the multi-product scheduling problem with batch and capacity constraint. This algorithm adopts the real number coding method and generates the initial population by means of the TS, which is expected to enha
语种	中文
其他标识符	672
内容类型	学位论文
源URL	[http://ir.ia.ac.cn/handle/173211/5738]
专题	毕业生_博士学位论文
推荐引用方式 GB/T 7714	王书锋. 成组加工生产系统中若干调度问题的研究[D]. 中国科学院自动化研究所. 中国科学院研究生院. 2002.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。