- 版本 (Version):20261019
- 原始碼版權 (Source Code Copyright):未知 (Unknown)——以 wurmen/Genetic-Algorithm-for-Job-Shop-Scheduling-and-NSGA-II 為基礎,該專案未宣告授權條款 (License)
- 散布限制 (Redistribution Restriction):本原始碼由立達軟體 (LEADERG INC.) 整合,請僅供私人使用,請勿散布至網際網路。(This source code is integrated by LEADERG INC. Please use it privately. Please DO NOT distribute it to internet.)
以基因演算法 (Genetic Algorithm) 進行零工式排程 (Job-shop Scheduling) 的命令列範例,支援 Windows 11、Ubuntu Linux 24.04 與 macOS 14+ (Apple Silicon)。在零工式排程問題中,每項工作都依自己的機台順序與處理時間,恰好經過每台機台一次;目標是最小化總完工時間 (Makespan)(最後一項工作完成的時間)。染色體 (Chromosome) 是一個作業序列,每個工作編號在每台機台上各出現一次;基因演算法以雙點交配 (Two-point Crossover) 加上修復步驟、位移突變 (Displacement Mutation) 與輪盤選擇 (Roulette-wheel Selection) 演化染色體,再將最佳排程繪製成依機台分列的互動式甘特圖 (Gantt Chart)(plotly HTML)。範例資料集為經典的 10×10 問題。不需要訓練或模型檔案,每次執行都會從頭開始搜尋。僅使用 CPU:基因演算法以純 Python + numpy 實作,所使用的函式庫(numpy、pandas、matplotlib、plotly、openpyxl)都沒有 GPU 後端(不使用 CUDA,也不使用 Apple GPU)。
[資料夾結構]
- CLAUDE.md / AGENTS.md:程式規格文件(內容相同)。
- CHANGELOG.md:版本變更紀錄 (Change Log)。
- copyright.txt:版權聲明。
- Data-Genetic-Algorithm-Job-Shop-Python.html:本說明文件(使用說明頁面)。
- 538.pdf:參考論文(用於排程的基因演算法)。
- data/job_shop/JSP_dataset.xlsx:兩個工作表:Processing Time 與 Machines Sequence,皆為 num_jobs × num_machines(範例:10×10)。
- model/job_shop/:執行輸出:result.txt、makespan.png(收斂曲線 (Convergence Curve))、gantt.html(互動式甘特圖 (Gantt Chart))。
- tool/tools.py:共用工具函式:project_root、delete_ipynb_checkpoints。
- src/:原始程式碼與啟動腳本 (Launcher Script)。
- venv/:Python 虛擬環境 (Virtual Environment),由 02_venv_create_windows/linux/mac 建立。
[執行環境需求]
- Python 3.14,由 01_python_install_windows.bat / 01_python_install_linux.sh / 01_python_install_mac.sh 安裝(Windows:winget;Ubuntu:apt,若 Ubuntu 套件庫沒有 python3.14 則改用 deadsnakes PPA;macOS:Homebrew)。
- 02_venv_create_windows.bat / 02_venv_create_linux.sh / 02_venv_create_mac.sh 會以 Python 3.14 建立 venv/,並從 src/requirements.txt 安裝 numpy、pandas、matplotlib、plotly 與 openpyxl(所有作業系統安裝相同的套件)。
- GPU:不需要。所有作業系統都只使用 CPU,因為基因演算法以純 Python + numpy 實作,而 numpy、pandas、matplotlib、plotly 與 openpyxl 都沒有 GPU 後端 (Backend);不需要 NVIDIA 驅動程式或 CUDA。
[操作步驟及說明]
每個步驟都同時提供 Windows 批次檔 (.bat) 與 shell 腳本(.sh,Linux 與 macOS 共用),兩者行為完全相同。所有啟動腳本 (Launcher Script) 都會先切換到專案根目錄,因此可從任何目錄執行。
1. 01_python_install_windows.bat / 01_python_install_linux.sh / 01_python_install_mac.sh
安裝 Python 3.14(winget / apt 或 deadsnakes PPA,需要 sudo / Homebrew)。若已安裝 Python 3.14 則略過安裝。在 Windows 上,安裝完成後請開啟新的終端機 (Terminal)。
2. 02_venv_create_windows.bat / 02_venv_create_linux.sh / 02_venv_create_mac.sh
刪除舊的 venv/,以 Python 3.14 建立全新的虛擬環境 (Virtual Environment),並安裝 src/requirements.txt。pip 失敗時會明確中止並顯示錯誤。
3. 03_venv_activate.bat / 03_venv_activate.sh
啟用虛擬環境 (Virtual Environment)。在 Linux/macOS 上請以 source 方式執行:source src/03_venv_activate.sh(bash 或 zsh)。若專案資料夾在建立虛擬環境之後被重新命名,請先用 02_venv_create_windows/linux/mac 重新建立虛擬環境;其他啟動腳本不需要啟用虛擬環境。
4. 04_run.bat / 04_run.sh
執行基因演算法零工式排程 (Job-shop Scheduling) 程式。額外參數會轉傳給 genetic_algorithm.py。
5. 99_venv_clean.bat / 99_venv_clean.sh
刪除 venv/ 資料夾。
6. 99_venv_deactivate.bat / 99_venv_deactivate.sh
在目前的 shell 中停用虛擬環境 (Virtual Environment)。在 Linux/macOS 上請以 source 方式執行:source src/99_venv_deactivate.sh(bash 或 zsh)。
[Python 程式進入點]
src/genetic_algorithm.py
--dataset job_shop --population-size 30 --crossover-rate 0.8 --mutation-rate 0.2 --mutation-selection-rate 0.2 --iterations 2000 [--seed N]。讀取 data/{dataset}/JSP_dataset.xlsx,顯示最佳作業順序(工作編號從 1 開始)、總完工時間 (Makespan) 與執行時間;並將 result.txt、makespan.png 與 gantt.html 寫入 model/{dataset}/。--seed 可讓執行結果重現。程式在 CPU 上執行(純 Python + numpy,沒有 GPU 後端);沒有 --device 選項。
[快速開始]
Windows 11
src\01_python_install_windows.bat
REM open a new terminal
src\02_venv_create_windows.bat
src\04_run.bat
Ubuntu 24.04
bash src/01_python_install_linux.sh
bash src/02_venv_create_linux.sh
bash src/04_run.sh
macOS 14+(Apple Silicon)
bash src/01_python_install_mac.sh
bash src/02_venv_create_mac.sh
bash src/04_run.sh
預設執行(族群 (Population) 30、2000 個世代 (Generation)、10×10 問題)只需數秒。由於基因演算法具有隨機性,每次執行的結果都會不同;傳入 --seed {n} 可得到可重現的結果,或提高 --iterations / --population-size 以取得更好的解。請以瀏覽器開啟 model/job_shop/gantt.html 檢視排程。
[資料集格式]
- data/{dataset}/JSP_dataset.xlsx 含兩個工作表,皆為 num_jobs 列 × num_machines 欄,另加開頭的索引欄:
- Processing Time:pt[j][k],工作 j 第 k 道作業的處理時間。
- Machines Sequence:ms[j][k],工作 j 第 k 道作業所在的機台(從 1 開始)。
- 若要排程自己的問題,請在 data/{name}/JSP_dataset.xlsx 中保持相同的工作表名稱 / 格式,並傳入 --dataset {name};工作數與機台數會依工作表的大小讀取。
[演算法說明(每個世代 (Generation))]
- 雙點交配 (Two-point Crossover)(機率 0.8):子代交換兩個隨機切點之間的片段。
- 修復 (Repair):交配可能破壞「每項工作在每台機台上恰好出現一次」的條件,因此會把某項工作多出的次數重新分配給出現次數不足的工作。
- 突變 (Mutation)(機率 0.2):隨機選出一組基因位置(mutation_selection_rate × 基因數),將其數值旋轉位移一格。
- 適應度 (Fitness):解碼後排程的總完工時間 (Makespan),數值越低越好。
- 選擇 (Selection):在親代 + 子代中以輪盤法 (Roulette Wheel) 選擇,權重為 1 / makespan。
程式會跨世代追蹤歷來最佳的順序(每個世代都會記錄,用於繪製收斂圖),並在最後輸出。
[參考資料]
- 原始程式碼儲存庫 (Repository)(wurmen):https://github.com/wurmen/Genetic-Algorithm-for-Job-Shop-Scheduling-and-NSGA-II
- 論文(隨附為 538.pdf):https://www.sciencedirect.com/science/article/abs/pii/0360835296000538
- plotly 甘特圖 (Gantt Chart):https://plotly.com/python/gantt/
執行後,即可看到基因演算法排程的結果。
這個 SDK 內建於 MYAI Studio 人工智慧開發工具。