摘要
讨论具有工件可拒绝的单机公共窗口指派单机排序问题,公共窗口指派指的是公共窗口的开始时间和窗口长度都是决策变量。如果工件在窗口期内完工,将不会产生任何额外费用,否则工件将会产生提前或者延误费用;若工件被拒绝,则会产生拒绝费用。目标是确定可加工的工件集、可加工工件集中的工件排列顺序与公共窗口的位置使得排序费用(包括提前、延误与公共窗口指派的费用)和拒绝费用的加权和最小,其中权重只与工件被排在序列中的位置有关,即位置权重。证明了此问题是多项式时间可解的,并给出了具体求解算法。
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.
作者
徐景孝
吕丹阳
王吉波
XU Jing-xiao;LYU Dan-yang;WANG Ji-bo(College of Science,Shenyang Aerospace University,Shenyang 110136,China)
出处
《沈阳航空航天大学学报》
2022年第2期91-96,共6页
Journal of Shenyang Aerospace University
基金
国家自然科学基金(项目编号:71471120)
辽宁省“兴辽英才计划”项目资助(项目编号:XLYC2002017)
辽宁省自然科学基金项目(项目编号2020-MS-233)。
关键词
单机
排序
拒绝工件
窗口指派
多项式时间
single-machine
scheduling
job-rejection
due-window assignment
polynomial time