摘要
本文讨论具有共同工期窗口的极小化极大值的单机排序问题,其中假设工件的加工时间与其开工时间成比例,即成比例恶化。费用函数由工件的提前惩罚、延误惩罚,工期窗口的开始时间和工期窗口的大小组成。目标是确定工件的开始加工时间、工件的一个最优排序、工期窗口的开始时间及工期窗口的规模大小,使得工件加工的最大费用函数达到最小。本文证明该问题是多项式时间可解的,并给出了具体求解解法。
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.
作者
薛静
王吉波
XUE Jing;WANG Ji-bo(School of Science,Shenyang Aerospace University,Shenyang 110136,China)
出处
《中国管理科学》
CSCD
北大核心
2023年第10期187-192,共6页
Chinese Journal of Management Science
基金
辽宁省“兴辽英才计划”资助项目(XLYC2002017)。
