流水車間調(diào)度問題PPT課件

1、6.2.9 遺傳算法的應(yīng)用流水車間調(diào)度問題浙江傳媒學(xué)院 王 忠6.2.9流水車間調(diào)度問題 Job Shop Scheduling Problem, JSP; 最經(jīng)典的幾個NP-hard問題之一。問題描述問題的約束條件1. 每個工件在機(jī)器上的加工順序是給定的。2. 每臺機(jī)器同時只能加工一個工件。3. 一個工件不能同時在不同的機(jī)器上加工。4. 工序不能預(yù)定。5. 工序的準(zhǔn)備時間與順序無關(guān)，且包含在加工時間中。6. 工件在每臺機(jī)器上的加工順序相同，且是確定的。 最大流程時間算法最大流程時間為最優(yōu)解為4-2-5-1-3設(shè)置工件4的前置任務(wù)為前一道工序設(shè)置機(jī)器1上各個工序的前置任務(wù)設(shè)置其它各個工序的前置

2、任務(wù)編碼與適應(yīng)度函數(shù)例6.1 Ho 和 Chang(1991) 給出的5個工件、4臺機(jī)器問題。 j1jt2jt3jt4jt工件131412530219553343234227641322141353355719 加工時間表（時間單位：s） 流水車間調(diào)度問題流水車間調(diào)度問題的解 最差解：1-4-2-3-5 最優(yōu)解：4-2-5-1-3 具體情況可參考相關(guān)視頻：請大家按順序觀看如下視頻 6.2.9.1-利用Project分析流水車間調(diào)度問題.mp4 6.2.9.2-最大流程時間算法的理解.mp4 6.2.9.3-遺傳算法求解流水車間調(diào)度問題的程序?qū)崿F(xiàn).mp4流水車間調(diào)度問題的編程實(shí)現(xiàn)1. 輔助工具類

3、 Random：隨機(jī)數(shù)產(chǎn)生器 IndexChooser：下標(biāo)選擇器流水車間調(diào)度問題的編程實(shí)現(xiàn)2、車間工件的表示 工序描述類Process； 工件描述類Job； 所有工作的管理類JobManager。流水車間調(diào)度問題的編程實(shí)現(xiàn)3、染色體的表示Chromosome 染色體中交叉運(yùn)算的實(shí)現(xiàn)FatherMotherChildAChildB流水車間調(diào)度問題的編程實(shí)現(xiàn) 染色體中交叉運(yùn)算CrossOver函數(shù)的實(shí)現(xiàn)FatherChildA的原型MotherChildAStartEnd流水車間調(diào)度問題的編程實(shí)現(xiàn) 染色體中交叉運(yùn)算CrossOver函數(shù)的實(shí)現(xiàn)FatherMotherChildAChildB流水車間調(diào)度問題的編程實(shí)現(xiàn) 染色體中變異運(yùn)算Mutation函數(shù)的實(shí)現(xiàn)：染色體中隨機(jī)產(chǎn)生兩個位置，交換這兩個位置的值交換流水車間調(diào)度問題的編程實(shí)現(xiàn) 種群的實(shí)現(xiàn)類Population6.2.9 遺傳