可動態(tài)生成具有優(yōu)先級工序集的Job-Shop調(diào)度算法.pdf

1、目前，很多學(xué)者都在嘗試用不同的方法來求解 Job-Shop 調(diào)度問題。但是由于Job-Shop 調(diào)度問題本身的復(fù)雜性，每種方法都存在著不足之處，如方法比較復(fù)雜或解的近優(yōu)性較差。 借鑒操作系統(tǒng)中進程(線程)調(diào)度算法的先進思想，設(shè)計一個新的相對簡潔的方法來求解Job-Shop調(diào)度問題的算法。Job-Shop 調(diào)度問題中的工序具有并發(fā)行、異步性等特點。因此，充分利用資源(機器)并且發(fā)揮工序的特點可以提高加工效率，縮短總的加工時間。首先

2、對 Job-Shop 調(diào)度問題進行建模，將單作業(yè)映射為加工樹；然后，借鑒操作系統(tǒng)中進程(線程)調(diào)度的先進思想，根據(jù)加工樹上的層來設(shè)置工序的優(yōu)先級；將工序分為不可調(diào)度工序、準(zhǔn)可調(diào)度工序和可調(diào)度工序，并動態(tài)的生成備選工序集；除了在工序需要動態(tài)調(diào)整的情況外，在調(diào)度過程中始終遵循著機器忙原則，即盡可能的讓機器不停的工作。調(diào)度工序時，從備選工序集中選擇工序，然后調(diào)度到機器上進行加工。選擇工序需要遵循四個調(diào)度策略，即優(yōu)先級策略、短用時策略、長路經(jīng)策

3、略和動態(tài)調(diào)整策略。成功調(diào)度一個工序后，從加工樹上刪除工序節(jié)點，再根據(jù)加工樹重新生成備選工序集。當(dāng)備選工序集為空時表明作業(yè)加工完畢。 同時，以根對齊方式將多個作業(yè)或動態(tài)加入的作業(yè)構(gòu)造成一棵虛擬加工樹的方法，從而簡化了Job-Shop調(diào)度問題。對于多作業(yè)Job-Shop調(diào)度問題或動態(tài) Job-Shop 調(diào)度問題，調(diào)度時按照本文設(shè)計的四種調(diào)度策略調(diào)度虛擬加工樹。通過實例驗證、比較，算法具有令人滿意的算法復(fù)雜度，而且近優(yōu)效果好。因此，算