没有合适的资源?快使用搜索试试~ 我知道了~
批处理机上具有两类释放时间的工件集竞争调度问题.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 2 浏览量
2023-02-23
20:13:36
上传
评论
收藏 121KB DOCX 举报
温馨提示
试读
14页
批处理机上具有两类释放时间的工件集竞争调度问题.docx
资源推荐
资源详情
资源评论
本文主要研究两个工件集合同时在一台批处理机上竞争加工的生产调度问题, 其中每
个集合的工件具有共同的释放时间.传统的生产调度研究主要集中在所有工件对应一个客户
需求, 作为一个整体考虑一致的性能指标.随着经济的发展和人们消费水平的提高, 顾客对
商品的个性化和多样化的需求越来越高, 所以这种传统的所有工件对应一致目标的生产调
度问题已不能再满足多客户需求情况下的生产调度问题, 因此迫切需要研究考虑多客户为
了自己的利益竞争使用共同资源的生产调度问题.此外, 在实际工业生产中为了提高机器利
用率、降低能耗等目的, 经常将具有相似特征的工件组批加工.本文从钢铁企业中提炼出这
类满足两个顾客需求的批处理机生产调度问题, 同时工件到达批处理机生产时具有两类不
同的到达时间.在钢铁工业的初轧厂中, 经过模铸生成的钢锭要先进入均热炉中加热或保温
一段时间, 使钢锭内部温度均匀达到轧制的要求, 而均热炉能同时加热多个钢锭可以看作一
台批处理机, 均热炉中一批的加工时间为炉中钢锭最长的均热时间.均热后的钢锭经轧制生
成的钢产品一部分直接销售给顾客, 一部分进入热轧阶段进行热轧(如图 1 所示).这里直接
销售给顾客与进行热轧的钢产品由于需求目的的不同, 对钢级的要求也不同, 所以在均热炉
中均热的温度与时间往往是不同的, 因此一般情况下目的相同的钢锭可以组成批进行均热,
而目的不同的钢锭不组成批, 即批是不可兼容的.此外, 两个不同目的的钢锭集合到达批处
理机上加工的到达时间可以看作两类不同的释放时间.基于上述初轧阶段的生产特点, 为了
满足两个不同目的的生产需求, 同时也为了提高初轧阶段的生产效率、降低能耗, 如何在批
处理机上对工件进行组批, 调度两个工件集合的加工顺序是至关重要的研究问题之一.
图 1 钢铁工业钢锭初轧过程
Fig. 1 Ingot rolling process in the steel industry
下载: 全尺寸图片 幻灯片
下面将给出一个具体的实例来解释我们所研究的一台批处理机上具有两类释放时间的
工件集竞争调度问题.在上面描述的钢锭初轧生产过程中, 假设热轧阶段需要 33 个钢产品,
对应的钢锭工件集合为 JA={JA1,JA2,JA3JA={J1A,J2A,J3A}.顾客需要直接购买 22 个钢产品,
对应的钢锭工件集合为.每个钢锭的加热时间分别为集合 JAJA 中工件的共同释放时间为
rA=0rA=0, 集合 JBJB 中工件的共同释放时间为 rB=2rB=2.批处理机的能力为 b=2b=2, 不同
集合的工件不能组成批加工.所考虑的目标函数为在满足集合 JBJB 中工件的最大完工时间
CBmaxCmaxB 不超过一个给定上界 QB=7QB=7 的约束下, 最小化集合 JAJA 中工件的最大完
工时间 CAmaxCmaxA.具体的参数介绍见第 1 节中问题描述.对于上述实例, 我们能获得一个
最优调度 ππ 满足 CBmax=6<QBCmaxB=6<QB 的条件下集合 JAJA 工件的最大完工时间最
小值为 CAmax=4CmaxA=4 (如图 2 所示).最优调度不仅满足了顾客的需求, 同时通过最小化
热轧阶段所需工件的最大完工时间, 为热轧阶段提高了生产效率.
图 2 最优调度 ππ
Fig. 2 The optimal schedule ππ
下载: 全尺寸图片 幻灯片
近几年来, 两个或多个工件集竞争调度的问题作为调度领域中多目标问题的特殊情况
备受学者们的关注, 其中每个工件集有各自的优化目标.不同目标工件集的存在使得问题的
求解比所有工件对应一个工件集的情况更加困难.多个工件集竞争的调度问题最初由 Baker
等
[1]
以及 Agnetis 等
[2]
提出, 前者研究了单机上最小化两个工件集目标函数线性组合形式问
题的复杂性, 后者研究了单机上依赖两个工件集不同目标函数的有约束优化形式及帕累托
形式问题的复杂性.关于多个工件集竞争的调度问题, 读者可参阅 Perez-Gonzalez 等
[3]
以及
Agnetis 等
[4]
.本文主要研究两个工件集目标函数有约束优化的形式, 即找到一个最优调度最
小化一个工件集的目标函数使得另一个工件集的目标函数不超过一个给定上界的问题.下面
主要针对两个工件集竞争的有约束优化调度问题进行简单综述.
关于单机批处理机上两个工件集竞争的调度问题, Li 等
[5]
提出了多项式或伪多项式时
间的算法来求解无界批处理机上批不可兼容与批可兼容两种情况下各种正则目标函数结合
的调度问题, 其中针对批不可兼容问题与分别提出了时间复杂度为
OO(nnAnBlog(QU−QL))(nnAnBlog(QU−QL))与(nnAnBP)(nnAnBP)的算法, 这里 IFIF 表示
批不可兼容, 具体参数请见文献[5]. Agnetis 等
[4]
针对无界批处理机上批不可兼容的问题与分
别提出了时间复杂度为与 OO(nA+n4B)(nA+nB4)的多项式时间算法. Fan 等
[6]
针对有界批处
理机上批不可兼容时问题提出了时间复杂度为 OO 的最优算法, 同时证明了上述问题当批
可兼容情况下以及批不可兼容情况下问题均为 NP—难问题.最近, Wang 等
[7]
研究了有界批
处理机上工件具有不同尺寸大小、加工时间相同的两个工件集竞争调度问题, 证明出目标
函数为最小化一个工件集的最大完工时间, 使得另一个工件集的最大完工时间不超过给定
上界问题, 不存在多项式时间算法具有常数的最坏情况比, 同时提出了一个有效算法获得最
优解的下界以及两个启发式算法对问题进行求解.虽然上面的文献考虑了批处理机上两个工
件集竞争的调度问题, 但所考虑的问题都是工件具有相同的释放时间. Tang 等
[8]
研究了单机
无界批处理机与有界批处理机上工件具有恶化加工时间的两个工件集竞争调度问题, 基于
批的兼容性与工件释放时间的差异性, 作者对一些目标函数的结合给出了时间复杂性, 其中
当批不可兼容且工件存在不同释放时间时, 针对批无界问题提出了时间复杂度为
(nAnBnlog(Q′U−Q′L))(nAnBnlog(QU′−QL′))的最优求解算法, 同时证明出批有界问题对于
批可兼容与不可兼容两种情况均为 NP—难问题, 具体参数请见文献[8].
关于单机上具有释放时间的两个工件集竞争调度问题, Yin 等
[9]
证明了问题为强 NP—
难问题, 并提出了分支定界算法进行求解. Lee 等
[10]
对问题提出了分支定界算法与遗传算法
进行求解. Wu 等
[11]
证明了问题为强 NP—难问题, 同时提出了分支定界算法、蚁群算法以及
遗传算法对问题进行求解. Cheng 等
[12]
对问题提出了分支定界算法以及模拟退火算法进行求
解.以上文献虽然考虑了工件带有不同的释放时间, 但都是利用智能算法对问题提出近优算
法进行求解, 没有从理论分析的角度对具有不同释放时间的两个工件集竞争调度问题进行
研究. Dover 等
[13]
研究了单机上工件具有相同加工时间与不同释放时间的两个工件集竞争调
度问题, 对各种正则目标函数的结合给出了时间复杂性.
另一方面, 关于批处理机上的调度问题也有许多学者研究.一台批处理机可以同时加工
多个工件, 一批的加工时间为该批中工件加工时间最大者, 同一批的所有工件同时开始加工
同时结束, 一旦一批开始加工就不能中断, 也不能再加入其他的工件到该批. Potts 等
[14]
对批
处理机上的调度问题进行了综述.根据批处理机的能力, 可以分为无界批处理机与有界批处
理机. Brucker 等
[15]
研究了单机批无界与批有界两种情况下工件具有相同释放时间的各种目
标函数的时间复杂性. Lee 等
[16]
研究了单机批处理机上工件具有不同释放时间, 目标函数为
最小化工件最大完工时间问题的时间复杂性, 对批无界情况提出了多项式时间动态规划算
法, 对批有界情况当工件具有两类释放时间时提出了伪多项式时间的动态规划算法进行求
解, 对一般情况提出了启发式算法. Liu 等
[17]
同样对于上述目标函数证明了批有界情况下问
题为 NP—难问题, 并对工件具有有限个释放时间情况提出了伪多项式时间算法, 对一般情
况设计了贪婪算法. Liu 等
[18]
针对有界批处理机上工件具有不同释放时间的最小化总完工时
间问题提出了一个多项式时间近似策略, 针对无界批处理机上工件具有不同释放时间的最
小化总加权完工时间问题提出了一个伪多项式时间近似策略.
综上, 目前还没有存在关于工件具有两类释放时间的两个工件集在批处理机上竞争调
度问题的研究, 虽然文献[8]中针对无界批处理机上批不可兼容情况下工件具有恶化加工时
间与不同释放时间时, 目标函数为最小化一个工件集的最大完工时间, 使得另一个工件集最
大完工时间不超过给定上界问题的一般情况提出了伪多项式时间求解算法, 但本文基于问
剩余13页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3651
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功