########## assembly_line_balancing.py ##########
import localsolver
import sys
#
# Functions to read the instances
#
def read_elem(filename):
with open(filename) as f:
return [str(elem) for elem in f.read().split()]
def read_instance(instance_file):
file_it = iter(read_elem(instance_file))
for i in range(3):
to_throw = next(file_it)
# Read number of tasks
nbTasks = int(next(file_it))
maxNbStations = nbTasks
for i in range(2):
to_throw = next(file_it)
# Read the cycle time limit
cycleTime = int(next(file_it))
for i in range(5):
to_throw = next(file_it)
# Read the processing times
processingTime = {}
for i in range(nbTasks):
task = int(next(file_it)) - 1
processingTime[task] = int(next(file_it))
for i in range(2):
to_throw = next(file_it)
# Read the successors' relations
successors = {}
while True:
try:
pred, succ = next(file_it).split(',')
pred = int(pred) -1
succ = int(succ) -1
if pred in successors:
successors[pred].append(succ)
else:
successors[pred] = [succ]
except:
break
return nbTasks, maxNbStations, cycleTime, processingTime, successors
#
# Modeling and solve
#
def main(instance_file, output_file, time_limit):
nbTasks, maxNbStations, cycleTime, processingTime, successors = read_instance(instance_file)
with localsolver.LocalSolver() as ls:
# Declare the optimization model
model = ls.model
# Decision variable : assignedStation[i] is the number of the station to which task i belongs
assignedStation = [model.int(0, maxNbStations-1) for i in range(nbTasks)]
# Intermediate expressions : nbUsedStations is the total number of used stations
stationUsed = [model.or_(model.eq(assignedStation[i] , s) for i in range(nbTasks)) for s in range(maxNbStations)]
nbUsedStations = model.sum(stationUsed)
# All stations must respect the cycleTime constraint
timeStations = [model.sum([model.eq(assignedStation[i] , s) * processingTime[i] for i in range(nbTasks)]) for s in range(maxNbStations)]
for s in range(maxNbStations):
model.constraint(timeStations[s] <= cycleTime)
# The stations must respect the succession's order of the tasks
for i in range(nbTasks):
if i in successors.keys():
for j in successors[i]:
model.constraint(assignedStation[i] <= assignedStation[j])
# Minimization of the number of stations
model.minimize(nbUsedStations)
model.close()
#
# Parameterize the solver
#
ls.param.time_limit = time_limit
# Initialize with a naive solution : each task belongs to one separate station
for i in range(nbTasks):
assignedStation[i].value = i
ls.solve()
# Write the solution in a file following the format:
# - 1st line: value of the objective
# - 2nd line: number of tasks
# - following lines: task's number, station's number
if output_file is not None:
with open(output_file, 'w') as f:
f.write("%d\n" % nbUsedStations.value)
f.write("%d\n" % nbTasks)
for i in range(nbTasks):
f.write("{},{}\n".format(i+1, assignedStation[i].value+1))
if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python assembly_line_balancing.py instance_file [output_file] [time_limit]")
sys.exit(1)
instance_file = sys.argv[1]
output_file = sys.argv[2] if len(sys.argv) >= 3 else None
time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 20
main(instance_file, output_file, time_limit)