具有恶化效应和共同工期窗口的极小化极大值单机排序问题  

Minmax Scheduling with Deterioration Effects and Common Due-window on a Single Machine

作　　者：薛静 王吉波 XUE Jing;WANG Ji-bo(School of Science,Shenyang Aerospace University,Shenyang 110136,China)

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

出　　处：《中国管理科学》2023年第10期187-192,共6页Chinese Journal of Management Science

基　　金：辽宁省“兴辽英才计划”资助项目(XLYC2002017)。

摘　　要：本文讨论具有共同工期窗口的极小化极大值的单机排序问题,其中假设工件的加工时间与其开工时间成比例,即成比例恶化。费用函数由工件的提前惩罚、延误惩罚,工期窗口的开始时间和工期窗口的大小组成。目标是确定工件的开始加工时间、工件的一个最优排序、工期窗口的开始时间及工期窗口的规模大小,使得工件加工的最大费用函数达到最小。本文证明该问题是多项式时间可解的,并给出了具体求解解法。Scheduling problems with deterioration effects(time-dependent processing times)have received increasing attention nowadays.In a real production environment,the processing time of each job often depends on its starting time,for example,a processing machine or a tool loses its qualities,i.e.,the later of a job starts,the longer it takes to process it,which is deterioration effect.In this paper,on one hand,the single machine scheduling problem is studied with a time-dependent deterioration model:the processing time of a job is proportional to its starting time,i.e.,pj=aj(A+Bsj),wherepj,sj,aj represent respectively,the actual processing time,starting time and deteriorating rate of the job Jj,while A and B are given positive constants.On the other hand,under the Just-In-Time(JIT)system,jobs are required to be completed as close as possible to their assigned due-windows,otherwise,earliness or tardiness penalty would be incurred.Under common due-window put forward in this paper,the cost function is composed of earliness penalty,tardiness penalty,due-window starting time and size.The goal is to determine the starting time of the first job,schedule of jobs,due-window starting time and size so that the maximum cost function is minimized.It is showed that this minmax problem can be modeled by a linear programming.Some properties of the optimal solution are analyzed,which proved that the problem can be solved in polynomial time O(n),where n is the number of jobs.Furthermore,a numerical example is given and the optimal solutions under different conditions are analyzed.Single machine minmax scheduling problem with deterioration effect and common due-window can impact the order in which the jobs are processed and thus affect production decisions.Therefore,it needs to take deterioration effect and due-window into consideration when making production decisions,and how to enhance production efficiency.

关 键 词：排序 极小化极大值 工期窗口安排 恶化效应 

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