I am working on a job scheduling program with the objective of reducing makespan that involves scheduling multiple jobs on multiple machines, where:
- The same job cannot operate on different machines at the same time
- Only one job can process at a given time on a given machine
However, I'd like to add a constraint that some machines may not be needed to process a particular job. As shown below, for the list of machine elements, job 1 can occur on machine 0 and 2, but doesn't need to go through machine 1 (it can skip this machine). To designate the null, I added np.nan. (Note: If you insert either 0, 1, or 2 here in place of np.nan, this entire code will run without errors.)
Here is my code so far:
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))
But I'm running into an error at this line:
# 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]]
Which says:
TypeError: list indices must be integers or slices, not float
Is it not possible to insert a missing value into the machine list for this type of Mixed Integer program? Or will a simple update to this line of code suffice?
As another attempt, I tried to add None instead of np.nan and this returned the error:
TypeError: list indices must be integers or slices, not NoneType
source https://stackoverflow.com/questions/70352814/is-there-a-way-to-ignore-some-machines-set-to-nothing-in-job-shop-scheduling-p
Comments
Post a Comment