Jag kommer att lösa två problem med hjälp av begränsningsprogrammering i denna handledning. Begränsningsprogrammering (CP) är en flexibel teknik som kan användas för att lösa problem avseende begränsningstillfredsställelse (CSP) som har fler eller färre genomförbara lösningar. CP-problem kan modelleras med godtyckliga begränsningar. CP fokuserar mest på variabler och begränsningar, man lägger inte så stort fokus på målfunktionen.
Begränsningsprogrammering används för planering, schemaläggning och tilldelning. Jag kommer att lösa ett problem med jobbschemaläggning och ett schemaläggningsproblem avseende husbyggnation i denna handledning. CP används främst för att hitta möjliga lösningar, jag kommer att försöka att hitta en optimal lösning. Jag använder Python och ortools-biblioteket från Google i denna handledning.
Jobbschemaläggningsproblem
En fabrik utför flera jobb i flera maskiner (Job Shop Problem) och målet är att hitta ett schema för varje maskin som minimerar den tid det tar för alla jobb att slutföras. Ett jobb har flera uppgifter som måste utföras i ordning och varje maskin kan bara hantera en uppgift åt gången. Resultatet från en körning visas nedanför koden.
# Import libraries
import collections
import ortools.sat.python.cp_model
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
# This class represent a task
class Task:
# Create a new task
def __init__(self, start:object, interval:object, end:object):
# Set values for instance variables
self.start = start
self.interval = interval
self.end = end
# This class represent an assignment
class Assignment:
# Create a new assignment
def __init__(self, job_id:int, task_id:int, start:int, duration:int):
# Set values for instance variables
self.job_id = job_id
self.task_id = task_id
self.start = start
self.duration = duration
# Sort
def __lt__(self, other):
return self.start + self.duration < other.start + other.duration
# Print
def __repr__(self):
return ('(Job: {0}, Task: {1}, Start: {2}, End: {3})'.format(self.job_id, self.task_id, self.start, self.start + self.duration))
# The main entry point for this module
def main():
# Input data: Task = (machine_id, duration)
jobs = [[(0, 3), (1, 2), (2, 2)], # Job0
[(0, 2), (2, 1), (1, 4)], # Job1
[(1, 4), (2, 3)] # Job2
]
# Variables
machine_count = 3
tasks = {}
intervals = collections.defaultdict(list)
assignments = collections.defaultdict(list)
# Compute horizon dynamically (sum of all durations)
horizon = sum(task[1] for job in jobs for task in job)
# Create a model
model = ortools.sat.python.cp_model.CpModel()
# Loop jobs
for job_id, job in enumerate(jobs):
# Loop tasks in a job
for task_id, task in enumerate(job):
# Variables
machine_id = task[0]
duration = task[1]
suffix = '_{0}_{1}'.format(job_id, task_id)
# Create model variables
start = model.NewIntVar(0, horizon, 'start' + suffix)
end = model.NewIntVar(0, horizon, 'end' + suffix)
interval = model.NewIntervalVar(start, duration, end, 'interval' + suffix)
# Add a task
tasks[job_id, task_id] = Task(start, interval, end)
# Add an interval for the machine
intervals[machine_id].append(interval)
# Add no-overlap constraints
# A machine can only work with 1 task at a time
for machine in range(machine_count):
model.AddNoOverlap(intervals[machine])
# Add precedence constraints
# Tasks in a job must be performed in the specified order
for job_id, job in enumerate(jobs):
# Loop tasks in a job
for task_id in range(len(job) - 1):
# Add a precedence constraint
model.Add(tasks[job_id, task_id + 1].start >= tasks[job_id, task_id].end)
# Create an objective function
objective = model.NewIntVar(0, horizon, 'makespan')
model.AddMaxEquality(objective, [tasks[job_id, len(job) - 1].end for job_id, job in enumerate(jobs)])
model.Minimize(objective)
# Create a solver
solver = ortools.sat.python.cp_model.CpSolver()
# Set a time limit of 30 seconds.
solver.parameters.max_time_in_seconds = 30.0
# Solve the problem
status = solver.Solve(model)
# Print output if the solution is optimal
if (status == ortools.sat.python.cp_model.OPTIMAL):
# Loop jobs
for job_id, job in enumerate(jobs):
# Loop tasks in a job
for task_id, task in enumerate(job):
# Add an assignment
machine_id = task[0]
start = solver.Value(tasks[job_id, task_id].start)
assignments[machine_id].append(Assignment(job_id, task_id, start, task[1]))
# Create bars and sort assignments
bars = []
for machine in range(machine_count):
assignments[machine].sort()
bar_tasks = []
for ass in assignments[machine]:
bar_tasks.append((ass.start, ass.duration))
bars.append(bar_tasks)
# Print the solution
print('--- Final solution ---\n')
print('Optimal Schedule Length: {0}\n'.format(solver.ObjectiveValue()))
print('Schedules:')
for machine in range(machine_count):
print(machine,':', *assignments[machine])
print()
# Plot gantt chart
fig, gnt = plt.subplots(figsize=(12, 8))
fig.suptitle('Gantt Chart', fontsize=16)
gnt.set_xlabel('Time')
gnt.set_ylabel('Machines')
gnt.set_yticks([12, 22, 32])
gnt.set_yticklabels(['0', '1', '2'])
gnt.grid(True)
# Loop bars
for i in range(len(bars)):
gnt.broken_barh(bars[i], (10 + i * 10, 4), facecolors=('tab:orange', 'tab:green', 'tab:red'))
j = 0
for x1, x2 in bars[i]:
gnt.text(x=x1 + x2/2, y= 12 + i * 10, s=j, ha='center', va='center', color='white')
j += 1
# Create a legend
labels = []
labels.append(mpatches.Patch(color='tab:orange', label='Task 0'))
labels.append(mpatches.Patch(color='tab:green', label='Task 1'))
labels.append(mpatches.Patch(color='tab:red', label='Task 2'))
plt.legend(handles=labels, loc=4)
# Show or save the plot
#plt.show()
plt.savefig('plots\\schedule-gantt.png')
# Tell python to run main method
if __name__ == '__main__': main()--- Final solution ---
Optimal Schedule Length: 11.0
Schedules:
0 : (Job: 0, Task: 0, Start: 0, End: 3) (Job: 1, Task: 0, Start: 3, End: 5)
1 : (Job: 2, Task: 0, Start: 0, End: 4) (Job: 0, Task: 1, Start: 4, End: 6) (Job: 1, Task: 2, Start: 7, End: 11)
2 : (Job: 1, Task: 1, Start: 5, End: 6) (Job: 0, Task: 2, Start: 6, End: 8) (Job: 2, Task: 1, Start: 8, End: 11)
Bygg fem hus
Detta är ett schemaläggningsproblem (husbyggnation) där 3 arbetare ska färdigställa 5 hus före en angiven tidpunkt. Varje arbetare har en viss färdighet för varje jobb och målet är att maximera den totala färdigheten för hela projektet. Resultatet från en körning visas nedanför koden, jobb i Gantt-schemat överlappar varandra på vissa ställen.
# Import libraries
import collections
import ortools.sat.python.cp_model
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
# This class represent a job
class Job:
# Create a new job
def __init__(self, duration:int, skills:[]):
# Set values for instance variables
self.duration = duration
self.skills = skills
# This class represent a task
class Task:
# Create a new task
def __init__(self, start:object, end:object):
# Set values for instance variables
self.start = start
self.end = end
# This class represent an assignment
class Assignment:
# Create a new assignment
def __init__(self, job:int, worker:str, start:int, duration:int, skill:int):
# Set values for instance variables
self.job = job
self.worker = worker
self.start = start
self.duration = duration
self.skill = skill
# Sort
def __lt__(self, other):
return self.start + self.duration < other.start + other.duration
# Print
def __repr__(self):
return ('{0}: {1}: {2}, Start: {3}, End: {4}'.format(str.title(self.job), self.worker, self.skill, self.start, self.start + self.duration))
# The main entry point for this module
def main():
# Variables
count_houses = 5
deadline = 400
workers = ['Joe', 'Jack', 'Jim']
jobs = {}
tasks = {}
worker_tasks = {}
precedences = []
intervals = collections.defaultdict(list)
assignments = collections.defaultdict(list)
objective = []
# Add jobs
jobs['masonry'] = Job(35, [9, 5, 0])
jobs['carpentry'] = Job(15, [7, 0, 5])
jobs['plumbing'] = Job(40, [0, 7, 0])
jobs['ceiling'] = Job(15, [5, 8, 0])
jobs['roofing'] = Job(5, [6, 7, 0])
jobs['painting'] = Job(10, [0, 9, 6])
jobs['windows'] = Job(5, [8, 0, 5])
jobs['facade'] = Job(10, [5, 5, 0])
jobs['garden'] = Job(5, [5, 5, 9])
jobs['moving'] = Job(5, [6, 0, 8])
# Add precedences
precedences.append(('masonry', 'carpentry'))
precedences.append(('masonry', 'plumbing'))
precedences.append(('masonry', 'ceiling'))
precedences.append(('carpentry', 'roofing'))
precedences.append(('ceiling', 'painting'))
precedences.append(('roofing', 'windows'))
precedences.append(('roofing', 'facade'))
precedences.append(('plumbing', 'facade'))
precedences.append(('roofing', 'garden'))
precedences.append(('plumbing', 'garden'))
precedences.append(('windows', 'moving'))
precedences.append(('facade', 'moving'))
precedences.append(('garden', 'moving'))
precedences.append(('painting', 'moving'))
# Create a model
model = ortools.sat.python.cp_model.CpModel()
# Loop houses
for house_id in range(count_houses):
# Loop jobs
for job_id, job in jobs.items():
# Variables
suffix = '_{0}_{1}'.format(house_id, job_id)
# Create model variables
start = model.NewIntVar(0, deadline, 'start' + suffix)
end = model.NewIntVar(0, deadline, 'end' + suffix)
# Add a task
tasks[house_id, job_id] = Task(start, end)
# Loop workers
allocation = []
for worker in range(len(workers)):
if(job.skills[worker] > 0):
suffix = '_{0}_{1}_{2}'.format(house_id, job_id, worker)
presence = model.NewBoolVar('precence' + suffix)
interval = model.NewOptionalIntervalVar(start, job.duration, end, presence, 'interval' + suffix)
worker_tasks[house_id, job_id, worker] = presence
intervals[worker].append(interval)
allocation.append(presence)
objective.append(job.skills[worker] * presence)
# One and only one worker must be assigned to a job
model.Add(sum(allocation) == 1)
# Add precedence constraints
for i, j in precedences:
model.Add(tasks[house_id, j].start >= tasks[house_id, i].end)
# Avoid overlapping between tasks of each worker
for worker in range(len(workers)):
model.AddNoOverlap(intervals[worker])
# Create an objective function
model.Maximize(sum(objective))
# Create a solver
solver = ortools.sat.python.cp_model.CpSolver()
# Set a time limit of 30 seconds.
solver.parameters.max_time_in_seconds = 30.0
# Solve the problem
status = solver.Solve(model)
# Print output if the solution is optimal
if (status == ortools.sat.python.cp_model.OPTIMAL):
# Loop houses
for house_id in range(count_houses):
# Loop jobs
for job_id, task in jobs.items():
start = solver.Value(tasks[house_id, job_id].start)
worker = 0
for w in range(len(workers)):
if(task.skills[w] > 0 and solver.Value(worker_tasks[house_id, job_id, w]) == 1):
worker = w
break
duration = task.duration
assignments[house_id].append(Assignment(job_id, workers[worker], start, duration, task.skills[worker]))
# Create bars and sort assignments
bars = []
for house_id in range(count_houses):
assignments[house_id].sort()
bar_tasks = []
for ass in assignments[house_id]:
bar_tasks.append((ass.start, ass.duration))
bars.append(bar_tasks)
# Print the solution
print('--- Final solution ---\n')
print('Optimal Total Skill: {0}\n'.format(solver.ObjectiveValue()))
for house_id in range(count_houses):
print('House:', house_id + 1)
print(*assignments[house_id], sep='\n')
print()
print()
# Plot gantt chart
fig, gnt = plt.subplots(figsize=(16, 8))
fig.suptitle('Gantt Chart', fontsize=16)
gnt.set_xlabel('Time')
gnt.set_ylabel('Houses')
gnt.set_yticks([12, 22, 32, 42, 52])
gnt.set_yticklabels(['1', '2', '3', '4', '5'])
gnt.grid(True)
# Loop bars
for i in range(len(bars)):
gnt.broken_barh(bars[i], (10 + i * 10, 4), facecolors=('tab:blue', 'tab:orange', 'tab:green', 'tab:red', 'tab:purple', 'tab:brown', 'tab:pink', 'tab:gray', 'tab:olive', 'tab:cyan'))
# Create a legend
labels = []
labels.append(mpatches.Patch(color='tab:blue', label='Masonry'))
labels.append(mpatches.Patch(color='tab:orange', label='Carpentry'))
labels.append(mpatches.Patch(color='tab:green', label='Plumbing'))
labels.append(mpatches.Patch(color='tab:red', label='Ceiling'))
labels.append(mpatches.Patch(color='tab:purple', label='Roofing'))
labels.append(mpatches.Patch(color='tab:brown', label='Painting'))
labels.append(mpatches.Patch(color='tab:pink', label='Windows'))
labels.append(mpatches.Patch(color='tab:gray', label='Facade'))
labels.append(mpatches.Patch(color='tab:olive', label='Garden'))
labels.append(mpatches.Patch(color='tab:cyan', label='Moving'))
plt.legend(handles=labels, loc=4)
# Show or save the plot
#plt.show()
plt.savefig('plots\\workers-gantt.png')
# Tell python to run main method
if __name__ == '__main__': main()--- Final solution ---
Optimal Total Skill: 385.0
House: 1
Masonry: Joe: 9, Start: 0, End: 35
Carpentry: Joe: 7, Start: 35, End: 50
Plumbing: Jack: 7, Start: 35, End: 75
Ceiling: Jack: 8, Start: 75, End: 90
Roofing: Jack: 7, Start: 90, End: 95
Windows: Joe: 8, Start: 95, End: 100
Garden: Jim: 9, Start: 95, End: 100
Painting: Jack: 9, Start: 95, End: 105
Facade: Joe: 5, Start: 100, End: 110
Moving: Jim: 8, Start: 110, End: 115
House: 2
Masonry: Joe: 9, Start: 50, End: 85
Carpentry: Joe: 7, Start: 110, End: 125
Plumbing: Jack: 7, Start: 105, End: 145
Ceiling: Jack: 8, Start: 145, End: 160
Roofing: Jack: 7, Start: 160, End: 165
Windows: Joe: 8, Start: 165, End: 170
Garden: Jim: 9, Start: 165, End: 170
Painting: Jack: 9, Start: 165, End: 175
Facade: Joe: 5, Start: 170, End: 180
Moving: Jim: 8, Start: 180, End: 185
House: 3
Masonry: Joe: 9, Start: 125, End: 160
Carpentry: Joe: 7, Start: 180, End: 195
Plumbing: Jack: 7, Start: 175, End: 215
Ceiling: Jack: 8, Start: 215, End: 230
Roofing: Jack: 7, Start: 230, End: 235
Windows: Joe: 8, Start: 235, End: 240
Garden: Jim: 9, Start: 235, End: 240
Painting: Jack: 9, Start: 235, End: 245
Facade: Joe: 5, Start: 240, End: 250
Moving: Jim: 8, Start: 250, End: 255
House: 4
Masonry: Joe: 9, Start: 195, End: 230
Carpentry: Joe: 7, Start: 250, End: 265
Plumbing: Jack: 7, Start: 245, End: 285
Ceiling: Jack: 8, Start: 285, End: 300
Roofing: Jack: 7, Start: 300, End: 305
Windows: Joe: 8, Start: 305, End: 310
Garden: Jim: 9, Start: 305, End: 310
Painting: Jack: 9, Start: 305, End: 315
Facade: Joe: 5, Start: 310, End: 320
Moving: Jim: 8, Start: 320, End: 325
House: 5
Masonry: Joe: 9, Start: 265, End: 300
Carpentry: Joe: 7, Start: 320, End: 335
Plumbing: Jack: 7, Start: 315, End: 355
Ceiling: Jack: 8, Start: 355, End: 370
Roofing: Jack: 7, Start: 370, End: 375
Windows: Joe: 8, Start: 375, End: 380
Garden: Jim: 9, Start: 375, End: 380
Painting: Jack: 9, Start: 375, End: 385
Facade: Joe: 5, Start: 380, End: 390
Moving: Jim: 8, Start: 390, End: 395