混合整數規劃排程問題模型最佳化

# 定義決策變數
x = {i: model.NewIntVar(0, upper_bound, f'x_{i}') for i in N}

# 定義目標函式
model.Minimize(sum(C[i] * x[i] for i in N))

# 新增滿足人員需求的約束
for t in T:
    model.Add(sum(M[t, i] * x[i] for i in N) >= R[t])

# 新增最小全職員工數量的約束
for i in N_f:
    model.Add(x[i] >= Q[i])

# 新增全職員工優先的約束
model.Add(sum(x[i] for i in N_f) == P)

def solve_model(M, nf, Q=None, P=None, no_part=False):
    s = newSolver('Staffing', True)
    nbt, n = len(M)-1, len(M[0])-1
    B = sum(M[t][-1] for t in range(nbt))
    x = [s.IntVar(0, B, "") for i in range(n)]
    
    # 基本約束條件
    for t in range(nbt):
        s.Add(sum([M[t][i] * x[i] for i in range(n)]) >= M[t][-1])
        
    if Q:
        for i in range(n):
            s.Add(x[i] >= Q[i])
            
    if P:
        s.Add(sum(x[i] for i in range(nf)) >= P)
        
    if no_part:
        for t in range(nbt):
            s.Add(B*sum([M[t][i] * x[i] for i in range(nf)]) >= sum([M[t][i] * x[i] for i in range(nf, n)]))
            
    s.Minimize(sum(x[i]*M[-1][i] for i in range(n)))
    rc = s.Solve()
    return rc, ObjVal(s), SolVal(x)

from ortools.linearsolver import pywraplp

def solve_model(D):
    # 建立求解器
    s = pywraplp.Solver('JobShopScheduling', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
    
    nJ, nM = len(D), len(D[0])
    M = sum([D[i][k][1] for i in range(nJ) for k in range(nM)])
    
    # 定義變數
    x = [[s.NumVar(0, M, '') for _ in range(nM)] for _ in range(nJ)]
    p = [[D[i][k][0] for k in range(nM)] for i in range(nJ)]
    d = [[D[i][k][1] for k in range(nM)] for i in range(nJ)]
    z = [[[s.IntVar(0, 1, '') for _ in range(nM)] for _ in range(nJ)] for _ in range(nJ)]
    T = s.NumVar(0, M, '')
    
    # 新增約束
    for i in range(nJ):
        for k in range(nM):
            s.Add(x[i][p[i][k]] + d[i][k] <= T)
            
            for j in range(nJ):
                if i != j:
                    s.Add(z[i][j][k] + z[j][i][k] == 1)
                    s.Add(x[i][p[i][k]] + d[i][k] - M * z[i][j][p[i][k]] <= x[j][p[i][k]])
                    s.Add(x[j][p[j][k]] + d[j][k] - M * z[j][i][p[j][k]] <= x[i][p[j][k]])
                    
        for k in range(nM - 1):
            s.Add(x[i][p[i][k]] + d[i][k] <= x[i][p[i][k + 1]])
    
    # 設定目標函式
    s.Minimize(T)
    
    # 求解模型
    rc = s.Solve()
    
    return rc, T.solution_value(), [[x[i][k].solution_value() for k in range(nM)] for i in range(nJ)]

#### 內容解密：
此程式碼實作了一個任務排程問題的數學模型，使用混合整數規劃來最小化整體完成時間。變數 `x`、`z`、`T` 分別表示任務的開始時間、任務之間的順序關係以及整體完成時間。約束條件確保了任務在不同機器上的正確執行順序以及避免機器之間的衝突。

### 高階排程技術

在實際應用中，任務排程問題往往涉及更複雜的條件和限制，例如資源限制、優先順序、動態到達時間等。為瞭解決這些問題，需要採用更先進的技術，如切斷法、列生成法等。

#### 切斷法（Cutting Stock Problem）

切斷法是一種常見的技術，用於解決資源分配和排程問題。它涉及將大問題分解成較小的子問題，並透過迭代求解這些子問題來獲得整體的最優解。

```plantuml
@startuml
skinparam backgroundColor #FEFEFE
skinparam defaultTextAlignment center
skinparam rectangleBackgroundColor #F5F5F5
skinparam rectangleBorderColor #333333
skinparam arrowColor #333333

title 切斷法（Cutting Stock Problem）

rectangle "分解" as node1
rectangle "求解" as node2
rectangle "整合" as node3

node1 --> node2
node2 --> node3

@enduml

# 簡化的切斷法範例
def cutting_stock_problem():
    # 假設的初始資料
    rolls = [100, 200, 300]  # 現有卷材長度
    demands = [50, 75, 100]  # 客戶需求
    
    # 簡化的求解過程
    solution = []
    for demand in demands:
        # 簡化處理，實際上需要更複雜的邏輯
        solution.append(min(rolls, key=lambda x: abs(x - demand)))
    
    return solution

#### 內容解密：
此範例展示了一個簡化的切斷法應用，用於滿足客戶對不同尺寸卷材的需求。透過遍歷客戶需求並選擇最接近的現有卷材尺寸，獲得了一個簡化的解決方案。實際應用中需要更複雜的演算法來最佳化資源分配。

## 切割庫存問題的數學模型與求解

### 問題描述

在紙張生產中，客戶訂單的寬度需求各異，如何從大卷紙張中切割出滿足客戶需求的小卷，同時最小化浪費，是切割庫存問題的核心。表7-1展示了一個隨機的訂單例項，第一列是訂單數量，第二列是所需的寬度（以產品卷寬度的百分比表示）。

### 模型建立

最初，人們透過指定各種切割模式來解決這一問題，但隨著技術的進步，我們可以將決定切割模式的任務交給求解器。

#### 決策變數

我們定義兩個主要的決策變數：
- $x_{i,j}$：表示從第j個大卷中切割出多少個滿足第i個訂單寬度需求的小卷。
- $y_j$：表示第j個大卷是否被使用。

#### 目標函式

目標是最小化使用的產品卷數量。為了避免求解器給出不連續的卷號，我們使用一個小技巧，使每個新卷的成本比前一個高：
\[ \min \sum_{j=1}^{K} j \cdot y_j \]
同時，我們引入一個輔助變數$t$，並新增約束$t = \sum_{j=1}^{K} y_j$，以便獲得實際使用的卷數。

#### 約束條件

1. **滿足客戶需求**：對於每個訂單$i$，我們需要確保從所有使用的卷中切割出的相應寬度的小卷數量不少於訂單需求$b_i$。
\[ \sum_{j=1}^{K} x_{i,j} \geq b_i, \forall i \]
2. **寬度限制**：對於每個大卷$j$，從中切割出的所有小卷的總寬度不能超過大卷的寬度（假設為100%）。
\[ \sum_{i=1}^{N} w_i \cdot x_{i,j} \leq 100 \cdot y_j, \forall j \]
這同時確保瞭如果$y_j = 0$，則$x_{i,j} = 0$，因為沒有被使用的卷不應有任何切割。

### 可執行模型

列表7-1展示瞭如何將上述模型轉換為可執行的程式碼（使用Python和某個最佳化求解器）。

```python
def solve_model(D):
    s, n = newSolver('CuttingStock', True), len(D)
    k, b = bounds(D)
    y = [s.IntVar(0, 1, '') for _ in range(k[1])]
    x = [[s.IntVar(0, b[i], '') for _ in range(k[1])] for i in range(n)]
    w = [s.NumVar(0, 100, '') for _ in range(k[1])]
    nb = s.IntVar(k[0], k[1], '')
    
    for i in range(n):
        s.Add(sum(x[i][j] for j in range(k[1])) >= D[i][0])
    
    for j in range(k[1]):
        s.Add(sum(D[i][1] * x[i][j] for i in range(n)) <= 100 * y[j])
        s.Add(100 * y[j] - sum(D[i][1] * x[i][j] for i in range(n)) == w[j])
        if j < k[1] - 1:
            s.Add(sum(x[i][j] for i in range(n)) >= sum(x[i][j + 1] for i in range(n)))
    
    Cost = s.Sum((j + 1) * y[j] for j in range(k[1]))
    s.Add(nb == s.Sum(y[j] for j in range(k[1])))
    s.Minimize(Cost)
    
    rc = s.Solve()
    rnb = SolVal(nb)
    return rc, rnb, rolls(rnb, SolVal(x), SolVal(w), D), SolVal(w)