摘要
讨论了带有工期窗口的单机排序问题。规定每个被接受的工件都有1个待定的交货期窗口,且所有工件的交货期窗口大小相同。工件的实际加工时间为与其开始时间和位置有关的指数函数。1个工件或者被拒绝,或者被接受。被拒绝就要支付拒绝的费用;被接受就会产生相应的提前、延误惩罚以及最大加工时间的惩罚。研究了2个问题,都需要确定工件的最优排序和窗口的开始时间,第1个问题的目标函数是与窗口的开始时间、窗口的大小、提前时间、延误时间、最大完工时间以及拒绝费用有关的函数。第2个问题的目标函数是与窗口的开始时间、窗口的大小、提前和延误的工件数、最大完工时间以及拒绝费用有关的函数。该问题在多项式时间可解,给出了问题的多项式时间算法。
This paper studies the single machine scheduling and due-window assignment problems with learning effect and deteriorating jobs.We assume that the jobs have multiple due windows.And all the due windows have the same size.The processing time of job are defined as functions of their start times and position in a sequence.A job will be rejected,or be accepted.The job which is refused have to pay the cost of the rejected.Jobs completed within the window incur no penalties,other jobs incur either earliness or tardiness penalties.The window location and size,along with the associated job schedule are to be determined to minimizes a certain cost function.The first function is made up of costs associated with the window location,window size,earliness,and tardiness and the makespan costs.The second function is made up of costs associated with the window location,window size,the number of earliness and tardiness jobs and makespan costs.We introduce a polynomial time algorithm for the problem.
出处
《沈阳师范大学学报（自然科学版）》
CAS
2017年第1期47-54,共8页
Journal of Shenyang Normal University:Natural Science Edition
基金
辽宁省教育厅科学研究一般项目(L2014433)
关键词
排序
单机
指数学习效应
交货期窗口
拒绝
scheduling
single machine
learning effect
due-window assignment
rejected
