具有共同窗口和可拒绝工件的排序问题  

The scheduling problem with common due-window and job-rejection

作　　者：王吉波 邓文龙 吕丹阳 李明慧 WANG Jibo;DENG Wenlong;LYU Danyang;LI Minghui(College of Science,Shenyang Aerospace University,Shenyang 110136,China)

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

出　　处：《沈阳航空航天大学学报》2024年第5期90-94,共5页Journal of Shenyang Aerospace University

基　　金：辽宁省教育厅基础科研项目(项目编号:JYTMS20230278)。

摘　　要：研究了同时具有可拒绝工件和共同窗口的单机排序问题,其中共同窗口的起始和结束时间都是决策变量。若工件在共同窗口期内加工完成,将不会产生额外费用,反之,则会产生提前或延误费用。对于被拒绝的工件,会有相应的拒绝费用。目标是确定哪些工件被接受或拒绝、接受加工的工作集合中的加工次序以及共同窗口的起始和结束时间,从而使得排序费用和拒绝费用的加权和最小,其中权重是位置权重。经过理论分析和算法设计,证明该问题存在时间复杂性更低的最优求解算法。It was considered that a single-machine scheduling problem with job-rejection and common due-window,which the starting time and finishing time of the common due-window were decision variables.If the job was completed in the common due-window,no additional cost would be incurred,otherwise,advance or delay costs would be incurred.If the job was rejected,a corresponding rejection cost wonld be incurred.The goal was to find out which jobs were accepted and rejected,the sequence of accepted job set,the starting and finishing times of common due-window,so as to minimize the weighted sum of scheduling cost and rejection cost,which the weights were the position weights.Through theoretical analysis and algorithm design,it is proved that there is an optimal solution algorithm with lower time complexity.

关 键 词：排序 可拒绝工件 单机 共同窗口 指派问题 

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