[Python] How can you use GRASP to solve a bi-objective optimization problem (in assembly line...

My problem is: I have to optimize my collaborative assembly line with solving a bi-objective optimization model using metaheuristics. We chose to start with GRASP.

The two objectives are to minimize costs (of workers and stataions) and energy (of robots)

I already did an optimization with Epsilon constraints and pareto front, so I know at least what to hope for. We get a trade of between good cost prediction and energy. I want to use GRASP method now to get better results, the code should chose wich operator (human/robot) does wich task (26 taks as a start) in wich mode (alone, collaboration, parallel), knowing that their speed (hte operators) change based on the mode thus the processing time changes also.

def greedy_random_construction(data: Dict, order: List[int], alpha: float, w_energy: float) -> List[List[Tuple[int, int]]]:

# list of stations; each station is a list of (task, mode)
station_tasks: List[List[Tuple[int, int]]] = []
# maintain metadata for the current station: (human_present, robot_present, load)
current_station = [] # tasks in current station
current_human = False
current_robot = False
current_load = 0.0


for j in order:
candidates = [] # list of tuples (objective_value, use_current, mode)
# evaluate placing task j into current station for each mode


for m in data['M']:
t = data['t_jm'][(j, m)]
e = data['E_jm'][(j, m)]
h, r = mode_flags(m)

# Option 1: assign to current station if it exists and capacity allows
if current_station and current_load + t <= data['T']:
cost_incr = 0.0
# additional worker or robot if not already present
if h and not current_human:
cost_incr += data['C_w']
if r and not current_robot:
cost_incr += data['C_c']
energy_incr = e
obj = cost_incr + w_energy * energy_incr
candidates.append((obj, True, m))

# Option 2: start new station (always feasible)
# opening a new station incurs C_s and costs for worker and robot as needed
cost_incr_new = data['C_s']
if h:
cost_incr_new += data['C_w']
if r:
cost_incr_new += data['C_c']
energy_incr_new = e
obj_new = cost_incr_new + w_energy * energy_incr_new
candidates.append((obj_new, False, m))

# construct and choose from restricted candidate list RCL
# find min and max objective among candidates
objs = [cand[0] for cand in candidates]
min_obj = min(objs)
max_obj = max(objs)
# define threshold
threshold = min_obj + alpha * (max_obj - min_obj)
rcl = [cand for cand in candidates if cand[0] <= threshold + 1e-12]
chosen_obj, use_current, chosen_m = random.choice(rcl)

# assign task j with chosen mode
t = data['t_jm'][(j, chosen_m)]
e = data['E_jm'][(j, chosen_m)]
h, r = mode_flags(chosen_m)
if use_current and current_station and current_load + t <= data['T']:
# add to current station
current_station.append((j, chosen_m))
current_human = current_human or h
current_robot = current_robot or r
current_load += t
else:
# close current station if it exists
if current_station:
station_tasks.append(current_station)
# start a new station
current_station = [(j, chosen_m)]
current_human = h
current_robot = r
current_load = t
# append last station
if current_station:
station_tasks.append(current_station)

return station_tasks


def local_search(station_tasks: List[List[Tuple[int, int]]], data: Dict, w_energy: float, max_iter: int = 1) -> List[List[Tuple[int, int]]]:

solution = [list(station) for station in station_tasks]


current_cost, current_energy = evaluate_solution(solution, data)
current_obj = current_cost + w_energy * current_energy

for _ in range(max_iter):
improved = False
# iterate over stations (index si) and tasks (index ti)
for si, station in enumerate(solution):
# compute station metadata: human/robot flags and load excluding each task
# Precompute station load and flags for reuse
station_load = sum(data['t_jm'][(j, m)] for j, m in station)
station_human = any(mode_flags(m)[0] for _, m in station)
station_robot = any(mode_flags(m)[1] for _, m in station)

for ti, (j, m) in enumerate(station):
# try all alternative modes
for m2 in data['M']:
if m2 == m:
continue

# compute new load if mode changes
t_old = data['t_jm'][(j, m)]
t_new = data['t_jm'][(j, m2)]
if station_load - t_old + t_new > data['T'] + 1e-9:
continue # exceeds capacity

# compute new human/robot flags
h_old, r_old = mode_flags(m)
h_new, r_new = mode_flags(m2)
# compute station human/robot flags after change
new_human = station_human
new_robot = station_robot
if h_old and not any((mode_flags(mk)[0] for k, (jk, mk) in enumerate(station) if k != ti)):
# old mode provided human but no other task requires human
new_human = h_new
else:
# other tasks provide human or old didn't provide, so OR with new
new_human = new_human or h_new
if r_old and not any((mode_flags(mk)[1] for k, (jk, mk) in enumerate(station) if k != ti)):
new_robot = r_new
else:
new_robot = new_robot or r_new

# compute cost and energy for this modified station and total solution
# Build a copy of solution with the changed mode
new_solution = [list(st) for st in solution]
new_solution[si][ti] = (j, m2)
# recompute evaluation (cost, energy)
new_cost, new_energy = evaluate_solution(new_solution, data)
new_obj = new_cost + w_energy * new_energy
if new_obj + 1e-9 < current_obj:
# accept move
solution = new_solution
current_obj = new_obj
current_cost = new_cost
current_energy = new_energy
improved = True
break

if improved:
break
if improved:
break
if not improved:
break
return solution

Continue reading...