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

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

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

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