约束规划无解求助：异构并行机调度CPLEX建模问题

关键错误点及修正方案 #

1. 数据不匹配错误 #

dat文件中numJobs=5，但setupTimes里包含了不存在的job6，超出Jobs范围（1..5），导致模型引用无效数据，破坏约束逻辑。
修正：删除setupTimes中所有包含job6的条目，仅保留job1-job5之间的转换数据。

2. 约束(5)逻辑完全错误 #

原数学模型约束(5)要求机器上的任务位置必须连续（若位置p+1有任务，则p必须有任务），但MOD文件中强制所有机器的每个位置p和p+1都必须有不同的job，意味着每台机器要填满5个位置，而5个job分给3台机器无法满足该约束，直接导致无可行解。
修正：替换原约束(5)为：

// 约束(5): 机器上的任务位置必须连续（若p+1有任务，则p必须有任务）
forall(m in Machines, p in 1..P-1)
    sum(j in Jobs) presenceOf(itvs[j][m][p+1]) <= sum(j in Jobs) presenceOf(itvs[j][m][p]);

3. 约束(6)与原数学模型完全背离 #

原模型中setup时间仅在job i紧随job j在同一机器上加工时生效，但MOD文件中的约束(6)强制所有job i的开始时间都必须晚于所有其他job j的完成时间加setup时间，这是错误的全局约束，导致job无法并行加工，必然无可行解。
修正：删除原约束(6)，重新实现原模型中W变量对应的逻辑：

// 实现原模型约束(6)(7)：同一机器上连续job的setup时间约束
forall(m in Machines, p in 1..P-1)
    forall(j in Jobs, i in Jobs: j != i) {
        // 当j在m的p位置，i在m的p+1位置时，i的开始时间 = j的完成时间 + setup时间
        startOf(itvs[i][m][p+1]) >= endOf(itvs[j][m][p]) + 
            sum(st in setupTimes: st.job1 == i && st.job2 == j && st.machine == m) st.time;
    }

4. 时间变量与interval变量关联错误 #

原MOD文件用max计算completionTimes，同时强制completionTimes >=所有interval的end，未被选中的optional interval（endOf未定义）会引发冲突，且逻辑冗余。
修正：绑定时间变量与选中的interval：

// 约束：startTimes和completionTimes与选中的interval绑定
forall(j in Jobs) {
    startTimes[j] == sum(m in Machines, p in Positions) presenceOf(itvs[j][m][p]) * startOf(itvs[j][m][p]);
    completionTimes[j] == sum(m in Machines, p in Positions) presenceOf(itvs[j][m][p]) * endOf(itvs[j][m][p]);
}

// 约束(8): interval长度等于对应机器的加工时间
forall(j in Jobs, m in Machines, p in Positions)
    lengthOf(itvs[j][m][p]) == sum(pt in processingTimes: pt.job == j && pt.machine == m) pt.time;

5. 目标函数与原模型不一致 #

原数学模型目标是最小化所有job的完成时间之和（ΣCj），但MOD文件中目标是最小化最大完成时间，若需对齐原模型，需修改目标：

// 原模型目标：最小化所有job完成时间之和
dexpr float totalCompletionTime = sum(j in Jobs) completionTimes[j];
minimize totalCompletionTime;

修正后的关键代码片段 #

修正后的MOD文件约束部分 #

subject to {
    // 约束(2): 每个job必须被分配到唯一的机器和位置
    forall(j in Jobs)
        sum(m in Machines, p in Positions) presenceOf(itvs[j][m][p]) == 1;

    // 约束(3): 仅能分配到可用机器
    forall(a in machineAvailabilities)
        forall(p in Positions)
            presenceOf(itvs[a.job][a.machine][p]) <= a.available;

    // 约束(4): 同一机器同一位置最多一个job
    forall(m in Machines, p in Positions)
        sum(j in Jobs) presenceOf(itvs[j][m][p]) <= 1;

    // 约束(5): 机器上的任务位置必须连续
    forall(m in Machines, p in 1..P-1)
        sum(j in Jobs) presenceOf(itvs[j][m][p+1]) <= sum(j in Jobs) presenceOf(itvs[j][m][p]);

    // 同一机器连续job的setup时间约束（对应原模型约束(6)(7)）
    forall(m in Machines, p in 1..P-1)
        forall(j in Jobs, i in Jobs: j != i) {
            startOf(itvs[i][m][p+1]) >= endOf(itvs[j][m][p]) + 
                sum(st in setupTimes: st.job1 == i && st.job2 == j && st.machine == m) st.time;
        }

    // 绑定时间变量与选中的interval
    forall(j in Jobs) {
        startTimes[j] == sum(m in Machines, p in Positions) presenceOf(itvs[j][m][p]) * startOf(itvs[j][m][p]);
        completionTimes[j] == sum(m in Machines, p in Positions) presenceOf(itvs[j][m][p]) * endOf(itvs[j][m][p]);
    }

    // 约束(8): interval长度等于加工时间
    forall(j in Jobs, m in Machines, p in Positions)
        lengthOf(itvs[j][m][p]) == sum(pt in processingTimes: pt.job == j && pt.machine == m) pt.time;
}

修正后的dat文件setupTimes部分 #

setupTimes = {
    // Machine 1上job1-job5之间的转换时间
    <1, 2, 1, 15>, <1, 3, 1, 15>, <1, 4, 1, 45>, <1, 5, 1, 45>,
    <2, 1, 1, 15>, <2, 3, 1, 15>, <2, 4, 1, 45>, <2, 5, 1, 45>,
    <3, 1, 1, 15>, <3, 2, 1, 15>, <3, 4, 1, 45>, <3, 5, 1, 45>,
    <4, 1, 1, 45>, <4, 2, 1, 45>, <4, 3, 1, 45>, <4, 5, 1, 15>,
    <5, 1, 1, 45>, <5, 2, 1, 15>, <5, 3, 1, 15>, <5, 4, 1, 15>
};

内容的提问来源于stack exchange，提问作者berkay orkun