运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2010年
2期
1-10
,共10页
运筹学%排序论%自由作业%稠密时间表%性能比%加工总长
運籌學%排序論%自由作業%稠密時間錶%性能比%加工總長
운주학%배서론%자유작업%주밀시간표%성능비%가공총장
Operations research%scheduling%open shop%dense schedule%performance ratio%makespan
对于自由作业问题,在安排工件时避免不必要空闲所得的时间表称为稠密时间表.稠密时间表的加工总长不超过最优值的……倍,是一个在机器数m>6时尚未被证明的猜想.本文通过引入工件与机器特征函数及机器关于工件非间断等概念,研究当最后完工机器至多有两个空闲区间时,性能比猜想成立的充分条件.
對于自由作業問題,在安排工件時避免不必要空閒所得的時間錶稱為稠密時間錶.稠密時間錶的加工總長不超過最優值的……倍,是一箇在機器數m>6時尚未被證明的猜想.本文通過引入工件與機器特徵函數及機器關于工件非間斷等概唸,研究噹最後完工機器至多有兩箇空閒區間時,性能比猜想成立的充分條件.
대우자유작업문제,재안배공건시피면불필요공한소득적시간표칭위주밀시간표.주밀시간표적가공총장불초과최우치적……배,시일개재궤기수m>6시상미피증명적시상.본문통과인입공건여궤기특정함수급궤기관우공건비간단등개념,연구당최후완공궤기지다유량개공한구간시,성능비시상성립적충분조건.
For open shop problem,if the principle of avoiding unnecessary machine idleness is applied when arranging jobs,a dense schedule is obtained.It is conjectured that the makespan of any dense schedule is at most 2-1/m times the optimal makespan of the problem,where m is the number of machines.The conjecture remains unproved when the number of machine is greater than six.In this paper,by introducing characteristic functions of jobs and machines and non-interruption of machines about jobs,we propose sufficient conditions under which the conjecture is true for general number of machines,provided that the last complete machine in the dense schedule has no more than two idle intervals.
