二机流水作业带不可用区间、工件可拒绝的调度问题

摘要：

考虑了二机流水作业第一台机器带不可用区间、工件可拒绝的调度问题.所有的工件都是加工可中断的,即当某一工件在不可用区间出现之前开始加工但在机器不可用时并未加工完成,在不可用区间结束后可以接着加工.目标函数是最小化接受加工工件的最大完工时间与拒绝工件的惩罚之和.此问题是NP-难的.首先提出了一个动态规划的最优算法以求解小规模问题,并给出了数值计算实例.所提出的动态规划算法的运算时间随着问题的规模成指数增长,进而又提出了一个启发式算法,并证明了该启发式算法的最坏性能比是3.

关键词：二机流水作业、调度、不可用区间、拒绝工件、动态规划

所属期刊栏目：26

分类号：TP30;F406;O221(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目71201104

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

页数：共6页

页码：473-478