1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
# vim: set fileencoding=utf-8 :
from gurobipy import *
class ILPUnsolvable (Exception):
pass
class ILPScheduler:
def __init__ (self, data):
"""
:param data: WorkerSlotModel
"""
self.data = data
self.model = Model("scheduling")
def optimize (self):
"""
Run optimization pass
"""
data = self.data
slotNames = data.slotNames
workerNames = data.workerNames
availability = { (w, s) : data.available (w, s) for w in workerNames for s in slotNames }
model = self.model
# x[(w,s)] == 1 if worker w is assigned to slot s
x = model.addVars(availability.keys(), ub=availability, vtype=GRB.BINARY, name='x')
# every worker needs slots
slotsPerWorker = model.addVars (workerNames, vtype=GRB.INTEGER, name='slotsPerWorker')
model.addConstrs((x.sum(w, '*') == slotsPerWorker[w] for w in workerNames), name='slotsPerWorkerConstr')
model.addConstrs((slotsPerWorker[w] >= data.minSlots (w) for w in workerNames), name='minSlotsPerWorkerConstr')
model.addConstrs((slotsPerWorker[w] <= data.maxSlots (w) for w in workerNames), name='maxSlotsPerWorkerConstr')
# but the number of worker per slot is limited
workerPerSlot = model.addVars (slotNames, vtype=GRB.INTEGER, name='workerPerSlot')
model.addConstrs ((x.sum('*', s) == workerPerSlot[s] for s in slotNames), name='workerPerSlotAssign')
model.addConstrs ((workerPerSlot[s] <= data.maxWorker (s) for s in slotNames), name='maxWorkerPerSlotConstr')
model.addConstrs ((workerPerSlot[s] >= data.minWorker (s) for s in slotNames), name='minWorkerPerSlotConstr')
# also the number of slots is limited
slotUsed = model.addVars (slotNames, vtype=GRB.BINARY, name='slotUsed')
for s in slotNames:
# slotUsed[s] is True iff there is at least one worker per slot
model.addGenConstrOr (slotUsed[s], [x[(w, s)] for w in workerNames], name='slotUsedConstr')
totalSlotsUsed = model.addVar (vtype=GRB.INTEGER)
model.addConstr (totalSlotsUsed == slotUsed.sum ('*'), name='totalSlotsUsedConstr')
model.addConstr(totalSlotsUsed >= data.minTotalSlots, name='minTotalSlotsUsedConstr')
model.addConstr(totalSlotsUsed <= data.maxTotalSlots, name='maxTotalSlotsUsedConstr')
# optimize for these constraints, more important first
# - similar-sized slots: minimize diff of each workerPerSlot and
# maxWorkerPerSlot. minimizing maxWorkerPerSlot is not sufficient,
# because solution 4/4/1 and 3/4/2 are the same
maxWorkerPerSlot = model.addVar (vtype=GRB.INTEGER)
# maxWorkerPerSlot=max(workerPerSlot)
model.addGenConstrMax (maxWorkerPerSlot, workerPerSlot, name='maxWorkerPerSlotConstr')
workerMaxDiff = model.addVars (slotNames, vtype=GRB.INTEGER, name='workerMaxDiff')
model.addConstrs ((workerMaxDiff[s] == maxWorkerPerSlot-workerPerSlot[s] for s in slotNames), name='workerMaxDiffConstr')
cost1 = model.addVar (vtype=GRB.INTEGER)
model.addGenConstrMax (cost1, workerMaxDiff, name='cost1Constr')
# - prefer solutions that fulfil most people’s wishes (everyone gets what he
# wants) by minimizing sum of priority.
totalPriority = model.addVar (vtype=GRB.INTEGER)
maxTotalPriority = 0
terms = []
for w in workerNames:
for s in slotNames:
p = data.priority (w, s)
if p is not None:
terms.append (x[w,s]*p)
maxTotalPriority += p
model.addConstr (totalPriority == quicksum(terms), 'totalPriority')
# - try to keep worker pairs together
# pairs = [(self.workers[0], self.workers[1])]
# terms = []
# for a, b in pairs:
# for j, s in enumerate (slotNames):
# terms.append (
# XXX: todo
# combine everything into a single cost function, because multi-objective
# solving sucks
totalCost = model.addVar (vtype=GRB.INTEGER)
# worker per slot is more important, so multiply with max sum of priority
model.addConstr (totalCost == cost1*maxTotalPriority + totalPriority, 'totalCost')
model.ModelSense = GRB.MINIMIZE
model.setObjective (totalCost)
model.optimize ()
status = model.Status
if status in (GRB.Status.INF_OR_UNBD, GRB.Status.INFEASIBLE, GRB.Status.UNBOUNDED):
raise ILPUnsolvable ()
if status != GRB.Status.OPTIMAL:
print ('not optimal')
print ('total priority is', totalPriority.X)
print ('max worker per slot is', maxWorkerPerSlot.X)
print ('cost1 is', cost1.X)
print ('total cost is', totalCost.X)
for s in slotNames:
print ('slotUsed', s, slotUsed[s].X)
print ('totalSlotsUsed', totalSlotsUsed.X)
return x, workerPerSlot
def firstNonNull (l):
for i in range (len (l)):
if l[i]:
return i
def mainOptimize (args):
import sys
from tabulate import tabulate
from model import WorkerSlotModel
# read data
with open (args.file, 'r') as fd:
data = WorkerSlotModel.fromYaml (fd)
sched = ILPScheduler (data)
try:
x, groupSize = sched.optimize ()
except ILPUnsolvable:
print ('unsolvable')
return
tbl = []
for w in data.workerNames:
r = [w]
for s in data.slotNames:
if groupSize[s].X > 0:
if x[w,s].X == 1:
r.append (data.priority (w, s))
else:
r.append ('')
tbl.append (r)
# skip row description, thus [1:]
tbl.sort (key=lambda x: firstNonNull (x[1:]))
hdr = []
for s in data.slotNames:
if groupSize[s].X > 0:
hdr.append ('{} ({})'.format (s, groupSize[s].X))
print (tabulate (tbl, headers=hdr))
def addParser (subparsers):
parser = subparsers.add_parser ('optimize', help='Optimize schedule')
parser.add_argument('file', help='input file')
parser.set_defaults (func=mainOptimize)
|