• 版本 (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)。

 

Data-Genetic-Algorithm-Job-Shop-inference-Jupyter.png

 

[資料夾結構]

  • 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))]

  1. 雙點交配 (Two-point Crossover)(機率 0.8):子代交換兩個隨機切點之間的片段。
  2. 修復 (Repair):交配可能破壞「每項工作在每台機台上恰好出現一次」的條件,因此會把某項工作多出的次數重新分配給出現次數不足的工作。
  3. 突變 (Mutation)(機率 0.2):隨機選出一組基因位置(mutation_selection_rate × 基因數),將其數值旋轉位移一格。
  4. 適應度 (Fitness):解碼後排程的總完工時間 (Makespan),數值越低越好。
  5. 選擇 (Selection):在親代 + 子代中以輪盤法 (Roulette Wheel) 選擇,權重為 1 / makespan。

程式會跨世代追蹤歷來最佳的順序(每個世代都會記錄,用於繪製收斂圖),並在最後輸出。

[參考資料]

 

執行後,即可看到基因演算法排程的結果。

 

這個 SDK 內建於 MYAI Studio 人工智慧開發工具。