example: scheduling, rework a bit
@@ -23,50 +23,42 @@ The objective of the job shop problem is to minimize the makespan:
the length of time from the earliest start time of the jobs to the latest end time.
"""
-jobs_data = [ # task = (machine_id: duration_time).
- {0:3,1:2,2:2},#job0
- {0:2,2:1,1:4},# job1
- {1:4,2:3} #job2
- ]
-machines_count = 1 + max([mach for job in jobs_data for mach in job.keys()])
-max_duration = sum([dur for job in jobs_data for dur in job.values()])
-
-jobs_count = len(jobs_data)
-all_jobs = range(jobs_count)
-all_machines = range(machines_count)
-
+jobs_data = cpm_array([ # (job, machine) = duration
+ [3,2,2], # job 0
+ [2,1,4], # job 1
+ [0,4,3], # job 2 (duration 0 = not used)
+])
+max_duration = sum(jobs_data.flat) # TODO, fixme
+jobs_count, machines_count = jobs_data.shape
start_time = intvar(0, max_duration, shape=(machines_count,jobs_count))
end_time = intvar(0, max_duration, shape=(machines_count,jobs_count))
+all_jobs = range(jobs_count)
+all_machines = range(machines_count)
+
model = Model()
# start + dur = end
-for j in all_jobs:
- for (m,dur) in jobs_data[j].items():
- model += (start_time[m,j] + dur == end_time[m,j])
+model += (start_time + jobs_data.T == end_time)
# Precedence constraint per job
-for j in all_jobs:
- for m1,m2 in combinations(jobs_data[j].keys(),2):
- model += (end_time[m1,j] <= start_time[m2,j])
+for m1,m2 in combinations(all_machines,2): # [(0,1), (0,2), (1,2)]
+ model += (end_time[m1,:] <= start_time[m2,:])
# No overlap constraint: one starts before other one ends
-for m in all_machines:
- for j1,j2 in (combinations(all_jobs, 2)):
- model += (start_time[m,j1] >= end_time[m,j2]) | \
- (start_time[m,j2] >= end_time[m,j1])
-
-makespan = Maximum(end_time)
+for j1,j2 in combinations(all_jobs, 2):
+ model += (start_time[:,j1] >= end_time[:,j2]) | \
+ (start_time[:,j2] >= end_time[:,j1])
+makespan = max(end_time)
model.minimize(makespan)
-val = model.solve()
-#print(model.status())
+#print(model.status())
+val = model.solve()
print("Makespan:",makespan.value())
print("Schedule:")
grid = -8*np.ones((machines_count, makespan.value()), dtype=int)
for j in all_jobs:
- for m in jobs_data[j]:
+ for m in all_machines:
grid[m,start_time[m,j].value():end_time[m,j].value()] = j
- #print(f"Job {j} starts at machine {m} at {start_time[m,j].value()} and ends at {end_time[m,j].value()}")
print(grid)
