具有学习效应的重新排序问题(运筹学与控制论)

重新排序问题是一种新型的排序模型,它有着重要的实际应用背景。生产部门根据自己的生产计划或是由客户提出的要求,在生产前一定时期内事先有一个作业方案,将已有的任务或订单按照某一规则安排好,使某一目标值最优。但是在即将开始生产之前或在生产过程中又有新的客户订单或任务到达。这时就要把新的任务和原有的还未加工的任务一起加工。为了不失信于对原客户的承诺或不耽误原任务的完成,这就要求在原有的工件或任务的次序不至于打乱得过多的前提下,使得总的目标函数值达到最优。本文考虑学习效应作用下的最小化总完工时间的重新排序问题,其中工件的加工时间是其所在序列加工位置有关的函数。对于最大序列错位、总序列错位和最大时间错位下的最小化总完工时间问题均给出了多项式时间算法,对于总时间错位下的最小化总完工时间问题提出了动态规划算法,并证明这个算法是拟多项式时间的。

Rescheduling Problems with Learning Effect

Rescheduling is one of significant modern scheduling models and it is motivated by important applications.The problem of rescheduling in the face of dynamically arriving orders is faced constantly by manufacturing companies.The manufacturing companies have been made their production schedules earlier according to their planes or some customers’ call,and scheduled the jobs by some rules to optimize some objective.However it frequently happens that additional orders arrived after a schedule has been developed,these orders must then be integrated into the schedule so as to optimize some measure of system performance without causing undue disruption in the shop.In this paper,I consider make span problems with rescheduling under the learning effect.The job processing times is defined by a function of its position in the sequence.For the maximum sequence disruption,the total sequence disruption and the maximum time disruption,some polynomial time algorithms for minimizing the total completion time problems are presented.For minimizing the total completion time problems,a dynamic programming algorithm is given under the total time disruption.Furthermore,it is showed that this algorithm is pseudpolynomial time algorithm.