序列相关Setup单机调度的最小化最大拖期分枝定界算法.pdf

1
2 2 2
2
1
第26卷第10期 进行处理之前已知 ; ③作业无优先级别 ,不可分割
种分枝定界算法求解单机序列相关 Setup 最大拖 作业 ; ④机器不能同时处理两个或多个作业; ⑤在
期问题 (简称 SDSM T) · t = 0 机器处理虚拟作业 0 ,并且 p0 = 0 , d0 = 0 , C0
= 0·s0 i , i ∈J , 取决于从处理作业 0 进入处理作
1 　问题描述 业 i 的费用 ,作业 0 和作业[0 ]都对应于虚拟作业
1. 1 　标记定义 0 ; ⑥sij + sjk ≥sik·
作业索引和集合 : 1. 3 　问题的数学描述
N 为作业处理总数 ; J 为所有作业的集合 , 假设有 N 项作业索引号从 1 到 N ,每项作业
J = { 1 ,2 ,3 , ⋯, N } ; J 0 = J ∪0 为处理作业的扩展 j ∈J 有处理时间 pj 、交货期 dj 和 Setup sij ·令 S
集合 ,包括一个虚拟作业 ,用“0”表示 ; i , j , k , l 为 = { [0 ] , [1 ] , [2 ] , ⋯, [ N ]} 为一个所有作业的调
处理作业索引号 , i , j , k , l ∈J 0 ; S 为以虚拟作业 度序列 ,序列 S 第 i 位置作业的拖期是
0 开始的序列 ,为问题的一个解 ; K 为以虚拟作业 T [ i ] = max{ C[ i ] - d [ i ] ,0} · (1)
0 开始的部分序列· 这里 , C[ i ]是作业[ i ]的完成时间 ,
收稿日期 : 2004 12 17
基金项目 : 国家自然科学基金资助项目(50205007) ; 东北大学“十五”学科建设项目·
作者简介 : 罗小川(1974 - ) ,男 ,四川西充人 ,东北大学副教授 ; 王成恩(1964 - ) ,男 ,黑龙江鸡西人 ,东北大学教授·
© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.