有没有办法在作业车间调度问题中忽略某些机器（设置为无）？
Is there a way to ignore some machines (set to nothing) in job shop scheduling problem?
我正在开发一个作业调度程序，该程序具有 objective 的缩短制造时间，涉及在多台机器上调度多个作业，其中：
- 同一个作业不能同时在不同的机器上运行
- 给定机器上给定时间只能处理一个作业
但是，我想添加一个约束条件，即处理特定作业可能不需要某些机器。如下图，对于机器元素列表，作业1可以出现在机器0和机器2上，但不需要经过机器1（可以跳过这台机器）。为了指定空值，我添加了 np.nan。 （注意：如果您在此处插入 0、1 或 2 代替 np.nan，则整个代码将 运行 没有错误。）
到目前为止，这是我的代码：
from pulp import *
import pandas as pd
import numpy as np
import collections as cl
from itertools import product
# define model
schedule = LpProblem(name="Minimize_Schedule", sense=LpMinimize)
# define number of machines (m) and jobs (n)
m = 3
n = 3
# for each job, the processing time of each
times = [[2, 1, 2],
[1, 2, 2],
[1, 2, 1]]
# for each job, the order the machines will go in
# for job 1, machine 1 is not needed
machines = [[0, np.nan, 2],
[1, 2, 0],
[2, 1, 0]]
# variables
# objective function to minimize (the makespan)
c = LpVariable(name="C")
# starting time x, on job j (from all jobs n) on machine i (from all machines m)
x = [[LpVariable(name='x({} ,{} )'.format(j+1, i+1), lowBound=0) for i in range(m)] for j in range(n)]
# y is a binary, where 1, if job j precedes job k on machine i; else 0
y = [[[LpVariable(name='y({} ,{} ,{} )'.format(j+1, k+1, i+1), cat="Binary") for i in range(m)] for k in range(n)] for j in range(n)]
# sum of total time for all machines (m) and jobs (n)
M = sum(times[i][j] for i in range(n) for j in range(m))
# add objective function to schedule model
schedule += c
# job j can only begin after job i has been completed
for (j, i) in product(range(n), range(1, m)):
schedule += x[j][machines[j][i]] - x[j][machines[j][i-1]] >= times[j][machines[j][i-1]]
# same jobs cannot occur at same time
for (j, k) in product(range(n), range(n)):
if k != j:
for i in range(m):
schedule += x[j][i] - x[k][i] + M*y[j][k][i] >= times[k][i]
schedule += -x[j][i] + x[k][i] - M*y[j][k][i] >= times[j][i] - M
for j in range(n):
schedule += c - x[j][machines[j][m-1]] >= times[j][machines[j][m-1]]
status = schedule.solve()
print(f"status: {schedule.status}, {LpStatus[schedule.status]}")
print("Completion time: ", schedule.objective.value())
for i,j in product(range(m),range(n)):
if x[i][j].varValue >= 0:
print("job %d starts on machine %d at time %g" % (i+1, j+1, x[i][j].varValue))
但是我运行在这一行遇到了一个错误：
# job j can only begin after job i has been completed
for (j, i) in product(range(n), range(1, m)):
schedule += x[j][machines[j][i]] - x[j][machines[j][i-1]] >= times[j][machines[j][i-1]]
其中说：
TypeError: list indices must be integers or slices, not float
这种混合整数程序不能在机器列表中插入缺失值吗？或者对这行代码进行简单更新就足够了吗？
作为另一次尝试，我尝试添加 None 而不是 np.nan，这返回了错误：
TypeError: list indices must be integers or slices, not NoneType
我认为您的表述存在一些问题（对于没有任何排除机器的模型）。它 runs/solves 对我来说是零值，所以我不确定你得到的结果是什么。但这是一个单独的问题。
如果您想在某些工作的上下文中“排除”某些机器，我认为您需要在索引方面做更多的工作。具体来说，如果你要写出一些约束的“数学”，你会做一些类似“对于计划中存在的每个作业-机器对 做一些约束...... “因此，我采用的方法是构建子集（根据需要）以仅包含有效的开始。下面的一个例子。另请注意，我喜欢使用 LpVariaible.dicts 方法来创建变量。我认为它更干净，然后你可以对它们进行元组索引，因为它们保存在字典中。
最后，术语的一些一致性将有助于提高可读性！当我认为您可以使用 j, j_prime, m, ...
解决此问题时，您有 i,j,k,m,n
from pulp import *
# define number of machines (m) and jobs (j)
machines = 3
jobs = 2
# for each job, the order the machines will go in
# for job 1, machine 1 is not needed
machine_sequence = [[0, None, 2],
[1, 2, 0 ]]
valid_starts = [(j, m) for j in range(jobs) for m in range(machines) if machine_sequence[j][m] != None]
model = LpProblem("Example", LpMinimize)
# Improved Variable...? using LpVariable.dicts
s = LpVariable.dicts("start time", indexs=valid_starts, lowBound=0, cat='Continuous')
# starting time x, on job j (from all jobs n) on machine i (from all machines m)
x = [[LpVariable(name='x({} ,{} )'.format(j+1, i+1), lowBound=0) for i in range(machines)] for j in range(jobs)]
print(type(s), s)
print(type(x), x)
# random constraint for j-m pairs that are valid
for j, m in valid_starts:
model += s[j, m] <= 10
编辑...部分模型（1 个约束）
我对此进行了更多修改。以您的方式处理您的数据，删除机器序列中的“None”更容易，因为您将需要遍历该序列。在时代中保留它只是为了将时代定位在正确的位置。不同的数据结构（字典）可能会导致不同的方法。
from pulp import *
# define model
schedule = LpProblem(name="Minimize_Schedule", sense=LpMinimize)
# define number of machines (m) and jobs (j)
machines = 3
jobs = 2
# for each job, the order the machines will go in
# for job 1, machine 1 is not needed
machine_sequence = [[0, 2],
[1, 2, 0 ]]
# for each job, the processing time of each
times = [[2, None, 3],
[1, 4, 5]]
valid_starts = [(j, m) for j in range(jobs) for m in machine_sequence[j]]
# x[j, m] = start time for job j on machine m
x = LpVariable.dicts("start time", indexs=valid_starts, lowBound=0, cat='Continuous')
# machine sequence constraint
# for each machine in the job sequence (except the 0th), the start time of the
# machine must be greater than the previous start + duration
for j in range(jobs): # for each job
for m_idx in range(1, len(machine_sequence[j])): # for each machine in job's seq, except 0
# convenience for bookkeeping...
curr_machine = machine_sequence[j][m_idx]
prior_machine = machine_sequence[j][m_idx - 1]
# so,
schedule += x[j, curr_machine] >= x[j, prior_machine] + times[j][prior_machine]
print(schedule)
产量：
Minimize_Schedule:
MINIMIZE
None
SUBJECT TO
_C1: - start_time_(0,_0) + start_time_(0,_2) >= 2
_C2: - start_time_(1,_1) + start_time_(1,_2) >= 4
_C3: start_time_(1,_0) - start_time_(1,_2) >= 5
VARIABLES
start_time_(0,_0) Continuous
start_time_(0,_2) Continuous
start_time_(1,_0) Continuous
start_time_(1,_1) Continuous
start_time_(1,_2) Continuous
编辑#2...一个完整的模型
下面是一个完整的模型，可以运行并（似乎）产生正确的答案。
# makespan model for jobs with sequence of machine requirements
# that may exclude some machines
from pulp import *
# define model
schedule = LpProblem(name="Minimize_Schedule", sense=LpMinimize)
# define number of machines (m) and jobs (j)
machines = 3
jobs = 2
# for each job, the order the machines will go in
# for job 1, machine 1 is not needed
machine_sequence = [[0, 2],
[1, 2, 0 ]]
# for each job, the processing time on required machines
times = [[2, None, 3],
[1, 4, 5]]
M=100
valid_starts = [(j, m) for j in range(jobs) for m in machine_sequence[j]]
# a convenience set that we will use later... job-job'-machine combos
# for jobs that both compete for the same machine
jjm = [(j, j_prime, m)
for j in range(jobs)
for j_prime in range(jobs)
for m in range(machines)
if j != j_prime
and (j, m) in valid_starts
and (j_prime, m) in valid_starts]
# x[j, m] = start time for job j on machine m
x = LpVariable.dicts("start time", indexs=valid_starts, lowBound=0, cat='Continuous')
# y[j, j_prime, m] = indicator that job j precedes j_prime on machine m
y = LpVariable.dicts("precedence", indexs=jjm, cat='Binary')
# makespan variable to capture the longest makespan
c = LpVariable("makespan", lowBound=0, cat='Continuous')
####### machine sequence constraint #######
# for each machine in the job sequence (except the 0th), the start time of the
# machine must be greater than the previous start + duration
for j in range(jobs): # for each job
for m_idx in range(1, len(machine_sequence[j])): # for each machine in job's seq, except 0
# convenience for bookkeeping...
curr_machine = machine_sequence[j][m_idx]
prior_machine = machine_sequence[j][m_idx - 1]
# so,
schedule += x[j, curr_machine] >= x[j, prior_machine] + times[j][prior_machine]
####### single-use constraint (jobs can't be on same machine at same time) #######
for j, j_prime, m in jjm:
# if y, job j precedes j_prime, if not, use big M
schedule += x[j, m] + times[j][m] <= x[j_prime, m] + (1-y[j, j_prime, m])*M
# one or the other case below must be true...
# aside: this is lazy as it will produce duplicates,
# but the solver will remove them
schedule += y[j, j_prime, m] + y[j_prime, j, m] == 1
####### constraint to capture the longest makespan #######
schedule += c # put the obj into model
for j, m in valid_starts: # for every job started on every machine...
schedule += c >= x[j, m] + times[j][m] # capture the latest finish time
#print(schedule)
status = schedule.solve()
print(f"status: {schedule.status}, {LpStatus[schedule.status]}")
print("Completion time: ", schedule.objective.value())
for j, m in valid_starts:
if x[j, m].varValue >= 0:
print("job %d starts on machine %d at time %g" % (j, m, x[j, m].varValue))
产量：
status: 1, Optimal
Completion time: 11.0
job 0 starts on machine 0 at time 0
job 0 starts on machine 2 at time 2
job 1 starts on machine 1 at time 0
job 1 starts on machine 2 at time 5
job 1 starts on machine 0 at time 10
流量。使用 1-index 作业...对不起触发器
使用 j,m 对的一些附加约束。
# constraint 2: makespan
for j in range(jobs):
for m_idx in range(1, len(machine_sequence[j])):
curr_machine = machine_sequence[j][m_idx]
prior_machine = machine_sequence[j][m_idx - 1]
schedule += c - x[j, prior_machine] >= times[j][prior_machine]
# constraint 3: only 1 job processing at a given time in a given machine
for j in range(jobs):
for m_idx in range(1, len(machine_sequence[j])):
curr_machine = machine_sequence[j][m_idx]
prior_machine = machine_sequence[j][m_idx - 1]
for k in range(jobs):
if j != k:
schedule += x[j, prior_machine] - x[k, prior_machine] >= times[k][prior_machine] - M*(1-y[j][k][m_idx])
schedule += x[k, prior_machine] - x[j, prior_machine] >= times[j][prior_machine] - M*(y[j][k][m_idx])
我正在开发一个作业调度程序，该程序具有 objective 的缩短制造时间，涉及在多台机器上调度多个作业，其中：
- 同一个作业不能同时在不同的机器上运行
- 给定机器上给定时间只能处理一个作业
但是，我想添加一个约束条件，即处理特定作业可能不需要某些机器。如下图，对于机器元素列表，作业1可以出现在机器0和机器2上，但不需要经过机器1（可以跳过这台机器）。为了指定空值，我添加了 np.nan。 （注意：如果您在此处插入 0、1 或 2 代替 np.nan，则整个代码将 运行 没有错误。）
到目前为止，这是我的代码：
from pulp import *
import pandas as pd
import numpy as np
import collections as cl
from itertools import product
# define model
schedule = LpProblem(name="Minimize_Schedule", sense=LpMinimize)
# define number of machines (m) and jobs (n)
m = 3
n = 3
# for each job, the processing time of each
times = [[2, 1, 2],
[1, 2, 2],
[1, 2, 1]]
# for each job, the order the machines will go in
# for job 1, machine 1 is not needed
machines = [[0, np.nan, 2],
[1, 2, 0],
[2, 1, 0]]
# variables
# objective function to minimize (the makespan)
c = LpVariable(name="C")
# starting time x, on job j (from all jobs n) on machine i (from all machines m)
x = [[LpVariable(name='x({} ,{} )'.format(j+1, i+1), lowBound=0) for i in range(m)] for j in range(n)]
# y is a binary, where 1, if job j precedes job k on machine i; else 0
y = [[[LpVariable(name='y({} ,{} ,{} )'.format(j+1, k+1, i+1), cat="Binary") for i in range(m)] for k in range(n)] for j in range(n)]
# sum of total time for all machines (m) and jobs (n)
M = sum(times[i][j] for i in range(n) for j in range(m))
# add objective function to schedule model
schedule += c
# job j can only begin after job i has been completed
for (j, i) in product(range(n), range(1, m)):
schedule += x[j][machines[j][i]] - x[j][machines[j][i-1]] >= times[j][machines[j][i-1]]
# same jobs cannot occur at same time
for (j, k) in product(range(n), range(n)):
if k != j:
for i in range(m):
schedule += x[j][i] - x[k][i] + M*y[j][k][i] >= times[k][i]
schedule += -x[j][i] + x[k][i] - M*y[j][k][i] >= times[j][i] - M
for j in range(n):
schedule += c - x[j][machines[j][m-1]] >= times[j][machines[j][m-1]]
status = schedule.solve()
print(f"status: {schedule.status}, {LpStatus[schedule.status]}")
print("Completion time: ", schedule.objective.value())
for i,j in product(range(m),range(n)):
if x[i][j].varValue >= 0:
print("job %d starts on machine %d at time %g" % (i+1, j+1, x[i][j].varValue))
但是我运行在这一行遇到了一个错误：
# job j can only begin after job i has been completed
for (j, i) in product(range(n), range(1, m)):
schedule += x[j][machines[j][i]] - x[j][machines[j][i-1]] >= times[j][machines[j][i-1]]
其中说：
TypeError: list indices must be integers or slices, not float
这种混合整数程序不能在机器列表中插入缺失值吗？或者对这行代码进行简单更新就足够了吗？
作为另一次尝试，我尝试添加 None 而不是 np.nan，这返回了错误：
TypeError: list indices must be integers or slices, not NoneType
我认为您的表述存在一些问题（对于没有任何排除机器的模型）。它 runs/solves 对我来说是零值，所以我不确定你得到的结果是什么。但这是一个单独的问题。
如果您想在某些工作的上下文中“排除”某些机器，我认为您需要在索引方面做更多的工作。具体来说，如果你要写出一些约束的“数学”，你会做一些类似“对于计划中存在的每个作业-机器对 做一些约束...... “因此，我采用的方法是构建子集（根据需要）以仅包含有效的开始。下面的一个例子。另请注意，我喜欢使用 LpVariaible.dicts 方法来创建变量。我认为它更干净，然后你可以对它们进行元组索引，因为它们保存在字典中。
最后，术语的一些一致性将有助于提高可读性！当我认为您可以使用 j, j_prime, m, ...
i,j,k,m,n
from pulp import *
# define number of machines (m) and jobs (j)
machines = 3
jobs = 2
# for each job, the order the machines will go in
# for job 1, machine 1 is not needed
machine_sequence = [[0, None, 2],
[1, 2, 0 ]]
valid_starts = [(j, m) for j in range(jobs) for m in range(machines) if machine_sequence[j][m] != None]
model = LpProblem("Example", LpMinimize)
# Improved Variable...? using LpVariable.dicts
s = LpVariable.dicts("start time", indexs=valid_starts, lowBound=0, cat='Continuous')
# starting time x, on job j (from all jobs n) on machine i (from all machines m)
x = [[LpVariable(name='x({} ,{} )'.format(j+1, i+1), lowBound=0) for i in range(machines)] for j in range(jobs)]
print(type(s), s)
print(type(x), x)
# random constraint for j-m pairs that are valid
for j, m in valid_starts:
model += s[j, m] <= 10
编辑...部分模型（1 个约束）
我对此进行了更多修改。以您的方式处理您的数据，删除机器序列中的“None”更容易，因为您将需要遍历该序列。在时代中保留它只是为了将时代定位在正确的位置。不同的数据结构（字典）可能会导致不同的方法。
from pulp import *
# define model
schedule = LpProblem(name="Minimize_Schedule", sense=LpMinimize)
# define number of machines (m) and jobs (j)
machines = 3
jobs = 2
# for each job, the order the machines will go in
# for job 1, machine 1 is not needed
machine_sequence = [[0, 2],
[1, 2, 0 ]]
# for each job, the processing time of each
times = [[2, None, 3],
[1, 4, 5]]
valid_starts = [(j, m) for j in range(jobs) for m in machine_sequence[j]]
# x[j, m] = start time for job j on machine m
x = LpVariable.dicts("start time", indexs=valid_starts, lowBound=0, cat='Continuous')
# machine sequence constraint
# for each machine in the job sequence (except the 0th), the start time of the
# machine must be greater than the previous start + duration
for j in range(jobs): # for each job
for m_idx in range(1, len(machine_sequence[j])): # for each machine in job's seq, except 0
# convenience for bookkeeping...
curr_machine = machine_sequence[j][m_idx]
prior_machine = machine_sequence[j][m_idx - 1]
# so,
schedule += x[j, curr_machine] >= x[j, prior_machine] + times[j][prior_machine]
print(schedule)
产量：
Minimize_Schedule:
MINIMIZE
None
SUBJECT TO
_C1: - start_time_(0,_0) + start_time_(0,_2) >= 2
_C2: - start_time_(1,_1) + start_time_(1,_2) >= 4
_C3: start_time_(1,_0) - start_time_(1,_2) >= 5
VARIABLES
start_time_(0,_0) Continuous
start_time_(0,_2) Continuous
start_time_(1,_0) Continuous
start_time_(1,_1) Continuous
start_time_(1,_2) Continuous
编辑#2...一个完整的模型
下面是一个完整的模型，可以运行并（似乎）产生正确的答案。
# makespan model for jobs with sequence of machine requirements
# that may exclude some machines
from pulp import *
# define model
schedule = LpProblem(name="Minimize_Schedule", sense=LpMinimize)
# define number of machines (m) and jobs (j)
machines = 3
jobs = 2
# for each job, the order the machines will go in
# for job 1, machine 1 is not needed
machine_sequence = [[0, 2],
[1, 2, 0 ]]
# for each job, the processing time on required machines
times = [[2, None, 3],
[1, 4, 5]]
M=100
valid_starts = [(j, m) for j in range(jobs) for m in machine_sequence[j]]
# a convenience set that we will use later... job-job'-machine combos
# for jobs that both compete for the same machine
jjm = [(j, j_prime, m)
for j in range(jobs)
for j_prime in range(jobs)
for m in range(machines)
if j != j_prime
and (j, m) in valid_starts
and (j_prime, m) in valid_starts]
# x[j, m] = start time for job j on machine m
x = LpVariable.dicts("start time", indexs=valid_starts, lowBound=0, cat='Continuous')
# y[j, j_prime, m] = indicator that job j precedes j_prime on machine m
y = LpVariable.dicts("precedence", indexs=jjm, cat='Binary')
# makespan variable to capture the longest makespan
c = LpVariable("makespan", lowBound=0, cat='Continuous')
####### machine sequence constraint #######
# for each machine in the job sequence (except the 0th), the start time of the
# machine must be greater than the previous start + duration
for j in range(jobs): # for each job
for m_idx in range(1, len(machine_sequence[j])): # for each machine in job's seq, except 0
# convenience for bookkeeping...
curr_machine = machine_sequence[j][m_idx]
prior_machine = machine_sequence[j][m_idx - 1]
# so,
schedule += x[j, curr_machine] >= x[j, prior_machine] + times[j][prior_machine]
####### single-use constraint (jobs can't be on same machine at same time) #######
for j, j_prime, m in jjm:
# if y, job j precedes j_prime, if not, use big M
schedule += x[j, m] + times[j][m] <= x[j_prime, m] + (1-y[j, j_prime, m])*M
# one or the other case below must be true...
# aside: this is lazy as it will produce duplicates,
# but the solver will remove them
schedule += y[j, j_prime, m] + y[j_prime, j, m] == 1
####### constraint to capture the longest makespan #######
schedule += c # put the obj into model
for j, m in valid_starts: # for every job started on every machine...
schedule += c >= x[j, m] + times[j][m] # capture the latest finish time
#print(schedule)
status = schedule.solve()
print(f"status: {schedule.status}, {LpStatus[schedule.status]}")
print("Completion time: ", schedule.objective.value())
for j, m in valid_starts:
if x[j, m].varValue >= 0:
print("job %d starts on machine %d at time %g" % (j, m, x[j, m].varValue))
产量：
status: 1, Optimal
Completion time: 11.0
job 0 starts on machine 0 at time 0
job 0 starts on machine 2 at time 2
job 1 starts on machine 1 at time 0
job 1 starts on machine 2 at time 5
job 1 starts on machine 0 at time 10
流量。使用 1-index 作业...对不起触发器
使用 j,m 对的一些附加约束。
# constraint 2: makespan
for j in range(jobs):
for m_idx in range(1, len(machine_sequence[j])):
curr_machine = machine_sequence[j][m_idx]
prior_machine = machine_sequence[j][m_idx - 1]
schedule += c - x[j, prior_machine] >= times[j][prior_machine]
# constraint 3: only 1 job processing at a given time in a given machine
for j in range(jobs):
for m_idx in range(1, len(machine_sequence[j])):
curr_machine = machine_sequence[j][m_idx]
prior_machine = machine_sequence[j][m_idx - 1]
for k in range(jobs):
if j != k:
schedule += x[j, prior_machine] - x[k, prior_machine] >= times[k][prior_machine] - M*(1-y[j][k][m_idx])
schedule += x[k, prior_machine] - x[j, prior_machine] >= times[j][prior_machine] - M*(y[j][k][m_idx])