具有老化效应的单机共同工期安排和工件可拒绝排序问题  

Due-date Assignment and Single Machine Scheduling with Aging Effect and Rejection

作　　者：刘春来 王建军 LIU Chun-lai;WANG Jian-jun(School of Management,Hangzhou Dianzi University,Hangzhou 310018,China;Faculty of Management and Economics,Dalian University of Technology,Dalian 116023,China)

机构地区：[1]杭州电子科技大学管理学院,浙江杭州310018 [2]大连理工大学管理与经济学部,辽宁大连116023

出　　处：《运筹与管理》2021年第7期66-70,135,共6页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(71901084,71672019,71421001);教育部人文社科基金资助项目(19YJC630099);浙江省自然科学基金资助项目(LQ19G020010);中央高校基本科研业务费资助(DUT21RW406);浙江省属高校基本科研业务费资助(GK199900299012-210)。

摘　　要：研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。This paper considers a single-machine scheduling and due date assignment problem.During the processing horizon,the processing time of a job depends on its position in a processing sequence and its aging effect and jobs also can be rejected by incurring penalties.The objective is to divide the jobs into a set of accepted and a set of rejected jobs,determine the sequence of accepted jobs and the location of maintenance activity so as to minimize the sum of the accepted jobs costs of earliness,tardiness,due date and the total penalty of the rejected jobs.We first provide a polynomial-time algorithm to solve the problem by translating it into assignment problem.We then prove a unified problem can be solved in polynomial time.Finally,we provide polynomial-time dynamic programming algorithms for the special case of the problem.

关 键 词：单机排序 拒绝 老化效应 维修活动 工期安排 

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