带有拒绝工件的公共窗口指派单机排序问题  

Common due-window assignment single-machine scheduling with job-rejection

作　　者：徐景孝 吕丹阳 王吉波 XU Jing-xiao;LYU Dan-yang;WANG Ji-bo(College of Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学理学院,沈阳110136

出　　处：《沈阳航空航天大学学报》2022年第2期91-96,共6页Journal of Shenyang Aerospace University

基　　金：国家自然科学基金(项目编号:71471120);辽宁省“兴辽英才计划”项目资助(项目编号:XLYC2002017);辽宁省自然科学基金项目(项目编号2020-MS-233)。

摘　　要：讨论具有工件可拒绝的单机公共窗口指派单机排序问题,公共窗口指派指的是公共窗口的开始时间和窗口长度都是决策变量。如果工件在窗口期内完工,将不会产生任何额外费用,否则工件将会产生提前或者延误费用;若工件被拒绝,则会产生拒绝费用。目标是确定可加工的工件集、可加工工件集中的工件排列顺序与公共窗口的位置使得排序费用(包括提前、延误与公共窗口指派的费用)和拒绝费用的加权和最小,其中权重只与工件被排在序列中的位置有关,即位置权重。证明了此问题是多项式时间可解的,并给出了具体求解算法。The single machine common due-window assignment scheduling problem with job-rejection is studied,where the common due-window assignment refers to that the starting time and size of the common due-window are decision variables.If the job is completed in the due-window,there will be no penalty,otherwise there will be a penalty for early or tardy.If a job is rejected,there is a rejection cost.The objective is to determine the sequence of accepted job set,the starting time and size of common due-window such that the weighted sum of scheduling cost(including earliness,tardiness,and common due-window assignment cost)and rejection cost to be minimized,where the weight only depends on its position scheduled,i.e.,position-dependent weight.It is proved that the problem can be solved in polynomial time,and the solution algorithm was proposed.

关 键 词：单机 排序 拒绝工件 窗口指派 多项式时间 

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