作业调度模具切换成本优化模型无可行解原因咨询

问题背景 #

有一组作业，每个作业对应一个模具，切换模具会产生成本，需要找到最小化切换成本的作业序列。已构建AMPL优化模型并编写Python实现，但无法得到可行解。

核心问题排查与修正 #

1. AMPL模型语法与变量定义错误 #

原模型变量定义存在语法缺陷，且取值范围不符合排列需求：

var sequence{JOBS} integer >=0,<jn

• 缺少分号，导致语法解析失败
• 取值范围<jn应改为<= jn-1，因为7个作业的排序位置应为0~6（共7个不同整数）

修正后变量定义：

var sequence{JOBS} integer >= 0, <= jn-1;

2. 目标函数逻辑倒置 #

原目标函数将sequence[k]错误理解为位置k对应的作业，但实际上sequence[i]表示作业i的排序位置。正确逻辑应为：当作业i的位置是k，作业j的位置是k+1时，计算两者的模具切换成本。

原错误目标函数：

minimize obj:sum{k in SHIFTJOBS, i in JOBS, j in JOBS}(if sequence[k]==i and sequence[k+1]==j then 1 else 0)*jobshiftcost[i,j];

修正后目标函数：

minimize obj: sum{k in SHIFTJOBS, i in JOBS, j in JOBS} 
    (if sequence[i] = k and sequence[j] = k+1 then 1 else 0) * jobshiftcost[i,j];

3. 约束条件错误 #

原no_overlap约束对所有i,j（包括i=j）要求sequence[i]>sequence[j] or sequence[i]<sequence[j]，但i=j时该条件永远不成立，直接导致模型不可行。正确的约束应为所有作业的排序位置互不相同：

subj to unique_positions{i in JOBS, j in JOBS: i != j}: sequence[i] != sequence[j];

4. Python中jobshiftcost构建逻辑冗余且错误 #

原代码通过嵌套循环构建jobshiftcost会导致重复赋值，正确方式应直接通过作业对应的模具映射获取切换成本：

原错误代码：

jobshiftcost = {(i, j): moldshiftcost[(k, l)].tolist() for (i, j) in jobpairs for (k, l) in moldpairs if
                (jobmold[i] - 1) == k and (jobmold[j] - 1) == l}

修正后代码：

jobshiftcost = {}
for i in JOBS:
    m_i = jobmold.iloc[i]["mold"] - 1  # 转换为0索引
    for j in JOBS:
        m_j = jobmold.iloc[j]["mold"] - 1
        jobshiftcost[(i, j)] = moldshiftcost[m_i][m_j]

修正后的完整代码 #

1. 修正后的AMPL模型（LPanelProduction.mod） #

set JOBS;
set jobpairs within {JOBS,JOBS};
set SHIFTJOBS;

param jobshiftcost{jobpairs};
param jn;

var sequence{JOBS} integer >= 0, <= jn-1;

minimize obj: sum{k in SHIFTJOBS, i in JOBS, j in JOBS} 
    (if sequence[i] = k and sequence[j] = k+1 then 1 else 0) * jobshiftcost[i,j];

subj to unique_positions{i in JOBS, j in JOBS: i != j}:
    sequence[i] != sequence[j];

2. 修正后的Python函数 #

def Lpanelproduction(jobmold, moldshiftcost):
    model = AMPL()
    model.read("LPanelProduction.mod")

    jn = len(jobmold)
    JOBS = range(jn)
    SHIFTJOBS = range(jn - 1)
    jobpairs = {(i, j) for i in JOBS for j in JOBS}

    model.param["jn"] = jn
    model.set["JOBS"] = JOBS
    model.set["SHIFTJOBS"] = SHIFTJOBS
    model.set["jobpairs"] = jobpairs

    # 转换为0索引的模具成本矩阵
    moldshiftcost = moldshiftcost.values
    # 构建作业切换成本
    jobshiftcost = {}
    for i in JOBS:
        m_i = jobmold.iloc[i]["mold"] - 1
        for j in JOBS:
            m_j = jobmold.iloc[j]["mold"] - 1
            jobshiftcost[(i, j)] = moldshiftcost[m_i][m_j]
    
    model.param["jobshiftcost"] = jobshiftcost

    return model

3. 求解代码 #

y = Lpanelproduction(jobmold, moldshiftcost)
y.solve(solver=SOLVER)
assert y.solve_result == "solved", y.solve_result

# 输出作业序列：按位置从小到大排列作业
sequence_vals = y.var["sequence"].values.to_dict()
sorted_jobs = sorted(sequence_vals.items(), key=lambda x: x[1])
print("最优作业序列（按执行顺序）：")
for idx, (job_idx, pos) in enumerate(sorted_jobs):
    print(f"位置{idx}: Job{job_idx+1} (模具{jobmold.iloc[job_idx]['mold']})")

y.display("sequence")

说明 #

修正后模型会生成一个作业排列，使得相邻作业的模具切换成本总和最小。例如，最优序列会将使用相同模具的作业连续安排，减少切换次数与成本。

内容的提问来源于stack exchange，提问作者Mentor Town