钢铁企业一类考虑恶化和运输的新型生产调度问题的理论研究

发布时间：2020-09-28 08:22

　　 钢铁工业是国民经济的重要支柱产业之一。近年来,随着建筑业、汽车制造业、造船业和家电业的大力发展,对钢材的需求数量和质量提出了更高的要求。由于钢铁生产具有多阶段、物件带有高温连续运作、物流呈交叉网状结构等特点,这就决定了物件在工序上的生产调度、连接工序之间的运输物流调度以及生产和物流调度的衔接都有严格的要求。合理进行生产和物流调度,有利于钢铁工业工序之间的物料紧凑衔接、减少中间等待时间,从而降低能耗、提高大型装置的设备利用率,达到降低生产和物流的综合成本、提高产品质量、提高钢铁工业竞争力的目的。 本文以钢铁企业的高能耗的炼钢和初轧为背景,分别从这两个工序中提炼出具有热链物流特征的生产和运输调度问题,进行理论研究。基于复杂性分析、算法最坏情况分析、多项式时间算法、近似策略、动态规划等多种技术手段,主要研究三个方面的问题：具有恶化特征的生产调度问题、生产和运输协调调度问题、考虑恶化特征的生产运输协调调度问题。 具体内容概括如下： 1)具有恶化特征的生产调度问题研究 (1)从钢锭在均热炉中加热的过程中提炼出工件带有释放时间和恶化特征的批处理机调度问题,其中工件在批处理机上的加工时间是工件在批处理机前的等待时间的一个分段函数,目标函数为最大完成时间的最小化。证明了该问题是NP-难问题。分别从相同的释放时间、批处理机能力无限以及工件具有优先次序三个方面,研究了三种特殊情况的多项式时间算法。 (2)从模铸到均热的生产过程提炼出了并行机和批处理机两阶段生产的恶化调度问题,其中工件的恶化是指工件在批处理机上的加工时间与工件在两阶段之间的等待时间有关。目标函数既考虑了两阶段生产的机器利用率,又考虑了批处理机的空载惩罚,即为最大完成时间和批处理机空余的惩罚费用之和的最小化。对于这个问题,证明了强NP-难性,提出了一个启发式算法,理论上分析了算法的最坏情况性能,并通过数值仿真实验,验证了算法性能的有效性。 2)生产和运输协调调度问题研究 (1)从钢锭的运输以及均热的过程受到启发,提炼出了多个台车生产前运输与批处理机生产的协调调度问题。目标函数为工件总完成时间与批处理机启动费用之和的最小化。首先利用划分问题证明了该问题是NP-难的,通过动态规划提出的伪多项式时间算法证明了该问题是一般意义NP-难问题。最后提出了解决问题的全多项式时间近似策略。而当工件在台车上的分配给定时,通过动态规划给出了多项式时间的最优算法。 (2)从模铸到均热的生产和运输中提炼出了二机之间带有运输考虑的二机流水调度问题,其中在运输的过程中考虑工件是否占有不同的物理空间两种情况。目标函数为最大完成时间的最小化。对于工件体积相同的情况,给出了最坏情况性能比为2的启发式算法。对于工件体积不相同的情况,给出了最坏情况性能比为7/3的启发式算法。 (3)从均热到初轧的生产过程提炼出了带有阻滞和运输时间考虑的两阶段生产调度问题,工件先在第一阶段批处理机上进行生产,当第二阶段的单机有空闲时才可以运输到第二阶段进行生产,如果单机不可利用,则批处理机上形成了阻滞。目标函数既考虑了工件的最大完成时间,又考虑了工件在批处理机上的总阻滞时间。对于总的阻滞时间的最小化问题,给出了多项式时间的最优算法。对于最大完成时间最小化问题,给出了强NP-难的证明,提出最坏情况性能比为2的启发式算法,实验结果证明了算法的有效性。对于最大完成时间和总阻滞时间的线性组合最小化问题,提出了混合整数规划模型,给出了强NP-难的证明,提出了启发式算法,并且从理论分析与实验结果两个方面验证了算法的有效性。 (4)从初轧生产到成品运输的过程提炼出了并行机生产与成品运输的协调调度问题。目标函数为工件总完成时间与运输费用之和的最小化。根据问题所满足的性质,通过过程划分及动态规划给出了解决问题的伪多项式时间算法,并且证明该问题是一般意义NP-难问题。对于工件在并行机上的分配给定的特殊情况,提出了多项式时间的最优算法。 (5)从钢锭在均热炉加热的前后生产过程提炼出了批处理机上生产与生产前后两阶段运输的协调调度问题。目标函数为工件的最大完成时间与批处理机启动费用之和的最小化。提出了问题的混合整数规划模型,给出了强NP-难证明。并且提出了最坏情况性能比为2的启发式算法,实验结果证明了算法的有效性。对于工件的加工次序确定的情况,给出了多项式时间的最优算法。 3)考虑恶化特征的生产运输协调调度问题研究 从均热车间中提炼出了工件生产前的运输以及批处理机生产的协调调度问题,其中也考虑了工件在批处理机的生产的恶化特征,这里的恶化是指工件在批处理机上的加工时间是关于工件的暴露时间的分段函数。目标函数为最大完成时间和批处理机的启动费用之和的最小化。证明了问题的一般情况以及批的数量受限的情况都是强NP-难问题,给出了启发式算法,并且进行了最坏情况性能比分析,实验结果也验证的算法的有效性。对于工件的完成时间受限的情况,证明了该问题也是强NP-难问题。对于工件的加工顺序给定的情况,给出了多项式时间最优算法。
【学位单位】：东北大学
【学位级别】：博士
【学位年份】：2009
【中图分类】：F273;F426.31;F224
【文章目录】：
摘要
Abstract
目录
第一章 绪论
    1.1 问题的研究目的及意义
        1.1.1 问题来源及研究目的
        1.1.2 问题背景及研究意义
    1.2 调度问题的一般理论方法
        1.2.1 调度问题的概述
        1.2.2 计算复杂性
        1.2.3 近似算法
        1.2.4 近似策略
        1.2.5 动态规划和整数规划
    1.3 调度问题的研究现状
        1.3.1 批处理机调度问题的研究现状
        1.3.2 具有恶化特征的调度问题的研究现状
        1.3.3 生产运输协调物流调度问题的研究现状
        1.3.4 本文研究的调度问题的创新点
    1.4 本文的研究路线及主要工作
        1.4.1 本文的研究路线
        1.4.2 本文的主要工作
第二章 工件带有释放时间的单个批处理机的恶化调度问题
    2.1 引言
    2.2 复杂性分析
    2.3 特殊情况
j=r,a_j|C_max'>        2.3.1 问题B|c,r_j=r,a_j|Cmax

        2.3.2 问题B|c=∞,r_j,a_j|C_max

        2.3.3 问题B|c,r_j,a_j,（?）|C_max

    2.4 小结
第三章 带有恶化特征的并行机与批处理机的两阶段调度问题
    3.1 引言
    3.2 问题描述
    3.3 复杂性分析
    3.4 启发式算法及性能比分析
    3.5 实验结果与数值计算
    3.6 小结
第四章 多个台车运输与批处理机生产的协调调度问题
    4.1 引言
    4.2 问题描述
    4.3 复杂性分析
    4.4 伪多项式时间算法
    4.5 全多项式时间近似策略（FPTAS）
    4.6 特殊情况
    4.7 小结
第五章 带有运输考虑的二机流水调度问题
    5.1 引言
2|s_j=1|C_max'>    5.2 问题TF₂|s_j=1|C_max

    5.3 问题TF₂|s_j|C_max

    5.4 小结
第六章 带有阻滞和运输时间考虑的两阶段流水调度问题
    6.1 引言
    6.2 问题描述
    6.3 混合整数规划模型
    6.4 复杂性分析
    6.5 特殊情况
    6.6 启发式算法及性能比分析
    6.7 实验结果与数值计算
    6.8 小结
第七章 两个并行机与批运输的协调调度
    7.1 引言
j+Dy'>    7.2 问题P2|T|∑C_j+Dy
    7.3 特殊情况
    7.4 小结
第八章 两阶段运输与批处理机生产的协调调度问题
    8.1 引言
    8.2 问题描述
    8.3 混合整数规划模型
    8.4 复杂性分析
    8.5 特殊情况
    8.6 启发式算法及性能分析
    8.7 实验结果与数值计算
    8.8 小结
第九章 带有恶化特征的运输和批处理机生产的协调调度问题
    9.1 引言
    9.2 问题描述
    9.3 文献综述
    9.4 复杂性分析
    9.5 多项式时间可解情况
    9.6 启发式算法及分析
    9.7 实验结果与数值计算
    9.8 小结
第十章 结束语
参考文献
致谢
作者博士期间发表和录用的论文
作者博士期间科研情况
个人简历

【共引文献】

相关期刊论文 前10条

1 齐学梅;;无等待流水调度问题迭代启发式算法[J];安徽师范大学学报(自然科学版);2009年01期

2 郭永辉;钱省三;;晶圆复杂制造系统在线优化调度系统研究[J];半导体技术;2007年04期

3 卓奕君;成晔;;面向大型产品装配的两维势能调度算法研究[J];北京信息科技大学学报(自然科学版);2009年04期

4 崔建双,李铁克,张文新;混合流水车间调度模型及其遗传算法[J];北京科技大学学报;2005年05期

5 李裕梅;谷云东;李洪兴;;调度问题Pm|p_j=1,intree|∑C_j的两个启发式算法[J];北京师范大学学报(自然科学版);2006年02期

6 袁芬;谷云东;尘非;;关于模糊工期平行机调度问题的若干结果[J];北京师范大学学报(自然科学版);2006年03期

7 孙秀平;谷云东;李洪兴;;任务无准备时间最小化加权最大延误单机调度问题的若干结果[J];北京师范大学学报(自然科学版);2006年05期

8 程贞敏;李洪兴;;允许中断的同速机调度问题的一个最优算法[J];北京师范大学学报(自然科学版);2008年05期

9 程贞敏;李洪兴;谷敏强;;最小化时间表长的平行机调度近似算法研究[J];北京师范大学学报(自然科学版);2012年01期

10 张淑娟;杨明明;韩翔凌;;带学习效应的供应链排序算法研究[J];滨州学院学报;2010年06期

相关会议论文 前10条

1 ;A Scheduling Problem on a Single Batching Machine with Batch Deliveries[A];中国自动化学会控制理论专业委员会D卷[C];2011年

2 ;On-line Scheduling with Rejection on Uniform Machines[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

3 柏庆国;张玉忠;;有尺寸的单机在线分批排序[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

4 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

5 张树霞;曹志刚;张玉忠;;极小化最大完工时间的离散可控排序(英文)[A];中国运筹学会第八届学术交流会论文集[C];2006年

6 闻振卫;;一类平行机上的任务指派问题及其动态规划算法[A];中国运筹学会第九届学术交流会论文集[C];2008年

7 陈荣军;唐国春;;自由作业环境下的供应链排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

8 王铮;周嵬;蔡砥;;设施区位:一个重要的科学问题[A];中国法学会经济法学研究会2005年年会专辑[C];2005年

9 ;Batch Delivery Scheduling with Limited Waiting Time Constraint on a Single Machine[A];2009中国控制与决策会议论文集（2）[C];2009年

10 ;Production-Transportation Scheduling Model on a Single Batching Machine[A];2009中国控制与决策会议论文集（2）[C];2009年

相关博士学位论文 前10条

1 马英;考虑维护时间的机器调度问题研究[D];合肥工业大学;2010年

2 李先锋;基于特征优化和多特征融合的杂草识别方法研究[D];江苏大学;2010年

3 钟雪灵;带强制工期非正则目标函数的排序问题研究[D];暨南大学;2010年

4 杨开兵;基于进化计算的多目标流水车间批组调度问题研究[D];大连理工大学;2011年

5 苗翠霞;分批排序及资源约束排序中若干问题[D];曲阜师范大学;2011年

6 柳春锋;工程项目中技能型员工调度问题研究[D];合肥工业大学;2011年

7 黎洁;容迟移动传感器网络中数据传输与数据管理机制的研究[D];中国科学技术大学;2011年

8 许瑞;基于蚁群优化算法的批调度问题研究[D];中国科学技术大学;2011年

9 杜冰;批处理机调度问题的模型与优化方法研究[D];中国科学技术大学;2011年

10 王磊;面向订单生产的供应链排序问题研究[D];暨南大学;2011年

相关硕士学位论文 前10条

1 张玮虹;生产管理中的若干排序问题[D];浙江理工大学;2010年

2 吴丽华;服装零售供应配送中的若干问题研究[D];浙江理工大学;2010年

3 任立莉;可拒绝平行批平行机与在线平行批两台一致机排序[D];郑州大学;2010年

4 孟令玉;基于网络流的开放式车间调度问题研究[D];哈尔滨工程大学;2010年

5 孙慧杰;码头泊位延迟问题的干扰管理模型研究[D];大连理工大学;2010年

6 周雁;基于遗传和粒子群优化算法的软硬件划分方法研究[D];华东师范大学;2011年

7 王悦;存在批处理设备的复杂产品调度研究[D];哈尔滨理工大学;2010年

8 于庆莲;基于静态并行时间确定可增加瓶颈设备的研究[D];哈尔滨理工大学;2010年

9 苏胜龙;带一个服务器的两台平行机半在线排序问题[D];华东理工大学;2011年

10 牟启燕;带一个服务器的两台机器自由作业排序问题的近似算法[D];华东理工大学;2011年

本文编号：2828564

boshi