考虑线性恶化效应的最小化总实际加工时间的单机在线调度问题  

Single Machine Online Scheduling with Linear Deterioration Effect to Minimize Total Actual Processing Time

作　　者：马冉 徐娟年 张玉忠 MA Ran;XU Juannian;ZHANG Yuzhong(Schoolof Management Engineering,Qingdao University of Technology,Qingdao 266525,China;Institute of Operations Research,School of Management,Qufu Normal University,Rizhao 276826,China)

机构地区：[1]青岛理工大学管理工程学院,山东青岛266525 [2]曲阜师范大学管理学院运筹学研究院,山东日照276826

出　　处：《运筹与管理》2023年第6期132-137,共6页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(11501171,11771251);山东省自然科学基金资助项目(ZR2020MA028)。

摘　　要：针对线材在制造过程中出现的加工时间随开工时间延长而延长的恶化现象,本文考虑了工件具有线性恶化效应的单机在线调度问题。工件以时间在线的方式到达,只有工件J_(j)到达后,决策者才知晓工件的基本信息,如基础加工长度b_(j)且工件才被允许加工。设定工件的实际加工时间P_(j)为其开工时间S_(j)的线性递增函数,即P_(j)=b_(j)+KS_(j),K>0。研究问题的目标是寻找最优在线调度算法以最小化所有工件的总实际加工时间。对于此问题,首先利用对手法证明了下界为2,随后运用新颖的“剥洋葱”分析方法证明了给出的算法的竞争比为2,即给出的算法是最好可能的在线算法,最后利用一个数值例子验证了所提出的算法在实际线材生产中的有效性。In typical wire rod production lines,the square billets are transported to a heating furnace to be heated to the desired rolling temperature,and then are hot-rolled into wire rods on a rolling machine.However,the rolling time of a square billet on a rolling machine is not a constant value and it relies on its starting temperature.In general,the temperature of the heated square billets drops by degrees,as the waiting time for rolling increases.This results not only in the wire head being prone to the cracks during the rolling process but also in a longer rolling time,as well as a greater rolling torque and rolling power,leading to large amounts of raw materials and energy consumption.The phenomenon that rolling time of a square billet increases as its waiting time for rolling increases is referred to as “deterioration effect”.In addition,wire orders from customers arrive unexpectedly and remain unexposed until they are placed with the steel plants,which is considered “online over time” or “online” for short in this work.How to schedule the heated square billets from “online” orders in rolling operation in order to mitigate the deterioration effect of square billets has become a crucial issue for wire manufacturers.In this work,we consider an interesting online scheduling problem on a single machine with linear deterioration effect.Especially,there are irrelevant jobs arriving online over time and the fundamental knowledge of each job J_j,such as its basic processing length b_j,is not revealed for the scheduler until it is released at time r_j.Also,the jobs become available for execution upon their respective release times.The actual processing time P_(j) of job J_(j) is assumed to be a linear increasing function of its starting time S_(j),i.e.,P_(j)=b_(j)+KS_(j),where K0.Note that at most one job can be executed on the machine at every point of time and interruption is disallowed.The objective of this scheduling problem is to devise an online schedule algorithm such that the total actual processing

关 键 词：单机 工程调度 在线 线性恶化 

分 类 号：O223[理学—运筹学与控制论]