How to achieve appliance duration with no interruptions
AnsweredHello everyone, just to preface this I am a complete beginner in python and gurobipy.
I am working on a code to optimize electricity cost for three appliances using mixed integer linear programming.
The result that I am getting is in the form of ones and zeroes based on the decision variable 'x' for each appliance at a given time slot k. k is the 96 15-minute time slots in a day. The question that I currently have is that I would like to know how to make the ones in the result come one after the other. In other words, I would like to have sequential processing for all the appliances, making sure that the ones come after the other with no interruption.
CODE:
#!/usr/local/bin/python3
from gurobipy import *
##Initialization:
#K (96 time slots for 1 day):
K = ['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']
# Duration (number of k slots) required for each appliance:
appliances, duration = multidict({
"WashingMachine": 6,
"ClothesDryer": 12,
"Dishwasher": 10,})
#Availability array for user time preference:
availability = tuplelist([
('WashingMachine', '20'),('WashingMachine', '21'),('WashingMachine', '22'),('WashingMachine', '23'),('WashingMachine', '24'),('WashingMachine', '25'),('WashingMachine', '26'),('WashingMachine', '27'),('WashingMachine', '28'),('WashingMachine', '29'),('WashingMachine', '30'),('WashingMachine', '31'),('WashingMachine', '32'),('WashingMachine', '33'),('WashingMachine', '34'),('WashingMachine', '35'),('WashingMachine', '36'),('WashingMachine', '37'),('WashingMachine', '38'),('WashingMachine', '39'),('WashingMachine', '40'),('WashingMachine', '41'),('WashingMachine', '42'),('WashingMachine', '43'),('WashingMachine', '44'),('WashingMachine', '45'),('WashingMachine', '46'),('WashingMachine', '47'),('WashingMachine', '48'),('WashingMachine', '49'),('WashingMachine', '50'),('WashingMachine', '51'),('WashingMachine', '52'),('WashingMachine', '53'),('WashingMachine', '54'),('WashingMachine', '55'),('WashingMachine', '56'),('WashingMachine', '57'),('WashingMachine', '58'),('WashingMachine', '59'),('WashingMachine', '60'),('WashingMachine', '61'),('WashingMachine', '62'),('WashingMachine', '63'),('WashingMachine', '64'),('WashingMachine', '65'),('WashingMachine', '66'),('WashingMachine', '67'),('WashingMachine', '68'),('WashingMachine', '69'),('WashingMachine', '70'),('WashingMachine', '71'),('WashingMachine', '72'),('WashingMachine', '73'),('WashingMachine', '74'),('WashingMachine', '75'),('WashingMachine', '76'),('WashingMachine', '77'),('WashingMachine', '78'),('WashingMachine', '79'),('WashingMachine', '80'),('ClothesDryer', '48'),('ClothesDryer', '49'),('ClothesDryer', '50'),('ClothesDryer', '51'),('ClothesDryer', '52'),('ClothesDryer', '53'),('ClothesDryer', '54'),('ClothesDryer', '55'),('ClothesDryer', '56'),('ClothesDryer', '57'),('ClothesDryer', '58'),('ClothesDryer', '59'),('ClothesDryer', '60'),('ClothesDryer', '61'),('ClothesDryer', '62'),('ClothesDryer', '63'),('ClothesDryer', '64'),('ClothesDryer', '65'),('ClothesDryer', '66'),('ClothesDryer', '67'),('ClothesDryer', '68'),('ClothesDryer', '69'),('ClothesDryer', '70'),('Dishwasher', '14'),('Dishwasher', '15'),('Dishwasher', '16'),('Dishwasher', '17'),('Dishwasher', '18'),('Dishwasher', '19'),('Dishwasher', '20'),('Dishwasher', '21'),('Dishwasher', '22'),('Dishwasher', '23'),('Dishwasher', '24'),('Dishwasher', '25'),('Dishwasher', '26'),('Dishwasher', '27'),('Dishwasher', '28'),('Dishwasher', '29'),('Dishwasher', '30'),('Dishwasher', '31'),('Dishwasher', '32'),('Dishwasher', '33'),('Dishwasher', '34'),('Dishwasher', '35'),('Dishwasher', '36'),('Dishwasher', '37'),('Dishwasher', '38'),('Dishwasher', '39'),('Dishwasher', '40'),('Dishwasher', '41'),('Dishwasher', '42'),('Dishwasher', '43'),('Dishwasher', '44'),('Dishwasher', '45'),('Dishwasher', '46'),('Dishwasher', '47'),('Dishwasher', '48'),('Dishwasher', '49'),('Dishwasher', '50'),('Dishwasher', '51'),('Dishwasher', '52'),('Dishwasher', '53'),('Dishwasher', '54'),('Dishwasher', '55'),('Dishwasher', '56'),('Dishwasher', '57')])
#Power rating for appliances according to their availability:
P = [0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4]
#Linking each nominal power to its appliance:
appliances, power = multidict({
"WashingMachine": 0.5,
"ClothesDryer": 0.4,
"Dishwasher": 0.4,})
#Linking indices for power:
Total_power = { w : P[i] for i,w in enumerate(availability) }
#Cost of electricity (TOU Tariff):
C = [0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.5,1,1,1,1,1,1,1,1,1,1,1,1,1,0.8,0.8,0.8,0.8,0.8,0.8,0.8,0.8,0.8,0.8,0.5,0.5,0.5,0.5,0.5,0.5,0.5,0.6,0.6,0.6,0.6,0.6,0.6,0.6,0.6,0.6,0.6,0.6,0.6,0.8,0.8,0.8,0.8,0.8,0.8,0.8,0.8,0.8,0.8,0.8,0.8,1,1,1,1,1,1,1,1,1,1,1,1,1]
#Linking the cost of electricity with K:
Cost = { w : C[i] for i,w in enumerate(availability) }
#MILP Model initialization:
model = Model("schedule")
#Decision Variables:
x = model.addVars(availability, ub=1, name="x")
#Objective Function: minimize cost of electricity
model.setObjective(quicksum(Cost[w,s]*x[w,s]*Total_power[w,s] for w,s in availability), GRB.MINIMIZE)
#Constraints:
#Each appliance must be ON for its full duration; not more & no less.
reqCts = model.addConstrs((x.sum(w,'*') == duration[w]
for w in appliances), "_")
#Optimize the model:
model.optimize()
print(x)
-
-
Gurobi Staff
Hi Aaesha,
It seems your durations are fixed, so your duration constraint can simply be written as `=1` and then variables represent the start time of the activity (you know that the end time is just the start time plus the duration). This is normally enough.
I think what you need is a precedence constraint (finish-to-start). This basically says activity `j` cannot start until `i` finishes. This can be enforced by the following constraint:
$$\sum_{t'=t} x_{it'} + \sum_{t'=0}^{t+d_i-1}x_{jt'} \leq 1~\forall t$$
where `x_{it}` is a binary variable with value 1 if activity `i` starts at time `t`, and `d_i` is the duration of the activity.
In your case, you need to declare `x` to be binary (as we can't turn half the washing machine on) and, for example, if you want the "WashingMachine" activity to be performed before the "ClothesDryer", I would write:# MILP Model initialization:
model = Model("schedule")
# Decision Variables:
x = model.addVars(availability, vtype=GRB.BINARY, name="x")
# Objective Function: minimize cost of electricity
model.setObjective(
quicksum(Cost[w, s] * x[w, s] * Total_power[w, s] for w, s in availability),
GRB.MINIMIZE,
)
# Constraints:
# Each appliance must be ON at least once (we know that it remains on for its duration)
reqCts = model.addConstrs((x.sum(w, "*") == 1 for w in appliances), name="assignment")
range_wm = range(20, 81) # just range of feasible washing machine start times
range_dryer = range(48, 71) # dryer start times
model.addConstrs(
(
sum(x["WashingMachine", str(td)] for td in range(t, range_wm[-1]))
+ sum(
x["ClothesDryer", str(td)]
for td in range(
range_dryer[0], min(range_dryer[-1], t + duration["WashingMachine"] - 1)
)
)
<= 1
for t in range_wm
), # range of times WashingMachine
name="precedence",
)
# Optimize the model:
model.optimize()
for k in availability:
if x[k].X > 0:
print(x[k])0 -
-
Hi David,
Thank you so much for your reply.
I agree that the duration can be specified by a single 1, and following duration plus end time can easily be determined. But because we want the program to calculate the cost for us, and we want it to consider the full duration when minimizing the cost, we need it to consider the full duration when it comes to the variable x, and print out all the slots where it would be ON for an appliance.
Is there any chance this aspect can still be maintained?
0 -
-
-
Of course, you can just associate the objective value of a given variable as the sum of the costs for the duration. i.e.
$$\textbf{min}~ \sum_i\sum_t \left(\sum_{t'=t}^{t+d_i} c_{it'}\right)x_{it}$$
Where `c_{it}` is the cost times power for you.
Also, another interpretation of your initial question, you can also exclude that no appliances can be on at the same time (and other similar constraints) using the exclusion:
$$\sum_i\sum_{t'=t-d_i+1}^t x_{it'} \leq 1 ~ \forall t$$
This will ensure that only one activity is being processed at any given time (including the whole duration of that activity).0 -
-
Hi David,
I will definitely take your suggestion and try it out. However, I was wondering if it is still possible to have a sequential, or consecutive, run of the appliances in the form of a constraint that can be added to my original code?
Thank you for your suggestions, and your patience.
0 -
-
-
Hi Aaesha,
That last constraint I mentioned does exactly that. In some order, the appliances will be sequential without any overlap. If only one appliance can be scheduled at any given time, your problem is a "single machine scheduling problem". And there are other, more efficient ways of modelling this, so I'd recommend you have a look at some scheduling literature: in [1] you can model this as a max-flow problem on page 173, [2] for a general overview.
The constraint would look like this:# Sample exclusion constraint. At most one appliance can be on at any given
# point in time and during the execution of that appliance.
model.addConstrs(
quicksum(
x[w, td]
for w in appliances
for td in range(max(t - duration[w], ranges[w][0]), ranges[w][-1])
)
<= 1
for t in range(1, 97)
)Where \(\texttt{ranges}\) is a dict of ranges indexed by appliance with the range of times when it can be processed.
Best,
David
[1] : Magnanti, T., Ahuja, R., and Orlin, J. (1993), Network flows: theory, algorithms, and applications, PrenticeHall, Upper Saddle River, NJ.
[2]: Brucker, P. and Knust, S. (2012), Complex Scheduling, GOR-Publications, 2nd edn, Springer, Berlin, Heidelberg.0 -
Please sign in to leave a comment.
Comments
5 comments