| 带固定工件的单机排序问题1｜FB, rj,pmtn｜∑j Uj的多项式算法 |
| |
| 引用本文： | 万国华,孙磊.带固定工件的单机排序问题1｜FB, rj,pmtn｜∑j Uj的多项式算法[J].运筹学学报,2009,13(2). |
| |
| 作者姓名： | 万国华 孙磊 |
| |
| 作者单位： | 1. 上海交通大学安泰经济与管理学院,上海,200052
2. 深圳大学管理学院,深圳,518060 |
| |
| 基金项目： | 国家自然科学基金，广东省自然科学基金 |
| |
| 摘 要： | 研究具有若干固定工件和自由工件,其中固定工件必须在指定时间窗内加工,而自由工件具有不同交工的时间,并且其加工可以中断的单机排序问题,其目标是极小化工件的误工数.该问题可以表示为1|FB,rj,pmtn|∑j Uj.首先讨论了问题的几个重要性质,以此为基础建立了求解该问题的动态规划算法,其时间复杂度为O(n4+m log m),其中m和n分别是固定工件数和自由工件数.
|
| 关 键 词： | 运筹学 排序 单机 延误工件数 交工时间 固定工件 中断抢先 多项式算法 |
Single Machine Preemptive Scheduling with Fixed Jobs and Release Dates to Minimize the Total Number of Tardy Jobs |
| |
| Wan Guohua,Sun Lei.Single Machine Preemptive Scheduling with Fixed Jobs and Release Dates to Minimize the Total Number of Tardy Jobs[J].OR Transactions,2009,13(2). |
| |
| Authors: | Wan Guohua Sun Lei |
| |
| Abstract: | A single machine scheduling problem with fixed jobs is considered, where the fixed jobs have to be scheduled in pre-specified time windows while the other jobs, called free jobs, have distinct release dates and are allowed to be preempted. The objective of the problem is to minimize the total number of tardy jobs. This problem can be denoted as 1|FB,rj,pmtn|∑j Uj. Several important properties of optimal solutions are discussed. Based on these properties, a dynamic program algorithm with time complexity 0(n4 + mlog m) is developed to solve the problem, where m and n are the numbers of fixed and free jobs, respectively. |
| |
| Keywords: | Operations research scheduling single machine number of tardy jobs release date fixed job preemption polynomial algorithm |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
