带有公共交货期窗口问询和退化工件的单机排序问题  

Scheduling Deteriorating Jobs on a Single Machine with a Common Due Window

作　　者：岳青 万国华[2] YUE Qing;WAN Guohua(School of Management,Shanghai University of International Business and Economics,Shanghai 201620,China;Antai College of Economics and Management,Shanghai Jiao Tong University,Shanghai 200052,China)

机构地区：[1]上海对外经贸大学工商管理学院,上海201620 [2]上海交通大学安泰经济与管理学院,上海200052

出　　处：《运筹与管理》2024年第5期48-54,共7页Operations Research and Management Science

基　　金：上海高校青年教师培训项目(ZZSUIBE16025)。

摘　　要：为了研究考虑公共交货期窗口问询的退化工件排序问题,构建了极小化因提前时间、延误时间以及交货期窗口问询产生的总成本的单机排序调度决策模型。模型假定所有工件的交货期窗口一致,且窗口的开始时间、窗口大小为决策变量;工件具有差异化的退化因子;工件的实际加工时间与其开始加工时间、退化因子呈线性关系。分析了交货期窗口决策和工件排序具有的最优性质,以及最优的工件排序与工件退化因子之间的关系,并提出了最优算法。研究表明:可基于工件的退化因子确定最优工件加工顺序,最优交货期窗口的开始时间和结束时间分别对应于最优序中某个工件的完工时间,研究问题可在多项式时间内进行求解。In operational systems of firms,scheduling significantly influences the performance.At the same time,with the application of just-in-time concept,due-date assignment also plays an important role in operational systems,which requires customer orders should be finished at a assigned time.In brief,through delicate scheduling rule and appropriate due-date assignment,firm’s limited production resource can be utilized more efficiently,and at the same time they can be better matched with varied customer demands.Thus,the decisions of scheduling and due-date assignment are usually decided simultaneously.However,for many practical application scenarios,it is allowable to complete customer orders within a period.Under these cases,decision makers need to determine due windows for customer orders instead of due dates.A due window for a job consists of three parts:the starting time of due window,the finishing time of due window and the due window size.In literature on due-window assignment scheduling problems,decision makers often assign the same due window for all customers to maintain a unified customer service policy.But the size of due window can be fixed directly by decision makers or can be negotiated with customers.In addition,the existing researches always assume jobs to be finished before the starting time of due window or after the finishing time of due window would incur cost due to earliness or tardiness,but jobs to be completed within due window would not result in any cost.Besides the influence of due window assignment method on formulating and solving due-window assignment scheduling problems,other interference factors existing in operational systems also exert an influence.Among these factors,jobs deterioration would change their actual processing times,and further influences the way the due-window assignment scheduling problem is solved.In the field of studies on due-window assignment scheduling problems with deterioration jobs,it is often assumed that the actual processing time of a job is a linear function

关 键 词：单机排序 公共交货期窗口 退化因子 多项式时间算法 

分 类 号：C935[经济管理—管理学]