具有学习效应的重新排序问题

摘要：

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

关键词：重新排序、学习效应、多项式时间算法

所属期刊栏目：29

分类号：O221.1(运筹学)

资助基金：天元基金11126348;重庆师范大学博士研究基金11XLB027

在线出版日期：2012-04-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1-6