单台机器有使用限制的排序问题

摘要：

研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.

关键词：排序、动态规划、使用限制、算法

所属期刊栏目：42

分类号：O223(运筹学)

资助基金：国家自然科学基金11126284

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

页码：18-21