1
$\begingroup$

Suppose we have two lines: L1 and L2.

Suppose we have 4 product types: A1, A2, B1 and B2.

Suppose the line capacity for both of the lines are 24 hours.

Suppose the changeover cost is

                   to
             A1  A2  B1  B2
        A1   0   1   4   4
 from   A2   1   0   4   4
        B1   4   4   0   1
        B2   4   4   1   0

Suppose the daily demand is

'A1':14 hours,
'A2':10 hours,
'B1':12 hours,
'B2':12 hours,

Suppose hours of one product type can be distributed over the two lines for production.

How could we use gurobi to come up with the best plan

L1: A1 ->cost 0-> A1 (14 hours) ->cost 1-> A2 (10 hours)
L2: A2 ->cost 4-> B1 (12 hours) ->cost 1-> B2 (12 hours)
Total changeover cost = 0 + 1 + 4 + 1 = 6

As a comparison, a suboptimal plan could be

L1: A1 ->cost 0-> A1 (14 hours) ->cost 4-> B1 (10 hours)
L2: A2 ->cost 0-> A2 (10 hours) ->cost 4-> B2 (12 hours) ->cost 1-> B1(2 hours)
Total changeover cost = 0 + 4 + 0 + 4 + 1 = 9

As a graphical illustration:

enter image description here

My code does not work as expected:

##############################################################################
##################  Production Scheduling with changeovers  ##################
##############################################################################

import os
import time
START_TIME = time.time()
import numpy as np
import pandas as pd
import gurobipy as gp
from gurobipy import GRB, quicksum, max_, and_, or_
from pathlib import Path
from matplotlib import pyplot as plt
from pathlib import Path

###############################   Inputs   ###################################

PRODUCTS = set(['A1','A2','B1','B2'])

LINES = set(['L1', 'L2'])

LAST_PRODUCTION = {
    'L1':'A1',
    'L2':'A2',
    }

DEMAND = {
    'A1':14,
    'A2':10,
    'B1':12,
    'B2':12,
    }

#   CHANGEOVER_COST 
#     A1  A2  B1  B2
# A1   0   1   4   4
# A2   1   0   4   4
# B1   4   4   0   1
# B2   4   4   1   0

CHANGEOVER_COST = {
    
    ('A1', 'A1'):0,
    ('A1', 'A2'):1,
    ('A1', 'B1'):4,
    ('A1', 'B2'):4,

    ('A2', 'A1'):1,
    ('A2', 'A2'):0,
    ('A2', 'B1'):4,
    ('A2', 'B2'):4,

    ('B1', 'A1'):4,
    ('B1', 'A2'):4,
    ('B1', 'B1'):0,
    ('B1', 'B2'):1,

    ('B2', 'A1'):4,
    ('B2', 'A2'):4,
    ('B2', 'B1'):1,
    ('B2', 'B2'):0
    
    }

LINE_CAPACITY = 24

###############################   Model   ###################################

model = gp.Model('production_scheduling_with_changeover')

hours = model.addVars(LINES, PRODUCTS)

flags = model.addVars(LINES, PRODUCTS, vtype = GRB.BINARY)

paths = model.addVars(LINES, PRODUCTS, PRODUCTS, vtype = GRB.BINARY)

# 1. Meet demand
meet_demand = model.addConstrs(
    (
     sum(hours[line, product] for line in LINES) == DEMAND[product] for product in PRODUCTS
    ),
    name = 'meet_demand_for_each_product'
)

# 2. Line capacity
capacity = model.addConstrs(
    (
     sum(hours[line, product] for product in PRODUCTS) <= LINE_CAPACITY for line in LINES
    ),
    name = 'line_capacity'
)

# 3. Constraints between flags and hours
for line in LINES:
    for product in PRODUCTS:
        model.addGenConstrIndicator(flags[line, product],
                                  0,
                                  hours[line, product] == 0
                                  
                                  )
        model.addGenConstrIndicator(flags[line, product],
                                  1,
                                  hours[line, product] >= 0
                                  )

# 4. Path


# 1. sum == N
path_1 = model.addConstrs(
    (
    sum(paths[line, p1, p2]  for p1 in PRODUCTS for p2 in PRODUCTS) == sum(flags[line, product] for product in PRODUCTS) for line in LINES
    ),
    name = 'total_paths'
)

# 2. no A -> B -> A
path_2 = model.addConstrs(
    (
    paths[line, p1, p2] +  paths[line, p2, p1] <= 1 for p1 in PRODUCTS for p2 in PRODUCTS for line in LINES if p1 != p2
    ),
    name = 'no_A_to_B_to_A'
)

#3. Diagonal 
  # Non-last type

path_3_1 = model.addConstrs(
    (
    paths[line, p, p] == 0 for p in PRODUCTS  for line in LINES if p != LAST_PRODUCTION[line]
    ),
    name = 'diagonal_0_for_non_last_type'
)

  # Last type
path_3_2 = model.addConstrs(
    (
    paths[line, p, p] == flags[line, p] for p in PRODUCTS for line in LINES if p == LAST_PRODUCTION[line]
    ),
    name = 'diagonal_for_last_type'
)



#4. Set 0 for non_production and non_last types

path_4_1 = model.addConstrs(
    (
    paths[line, p1, p2] <= flags[line, p1] for p1 in PRODUCTS for p2 in PRODUCTS for line in LINES if p1 != LAST_PRODUCTION[line] and p1 != p2
    ),
    name = 'shade_for_nonproduction_nonlast_types_row'
)

path_4_2 = model.addConstrs(
    (
    paths[line, p1, p2] <= flags[line, p2] for p1 in PRODUCTS for p2 in PRODUCTS for line in LINES if p2 != LAST_PRODUCTION[line] and p1 != p2
    ),
    name = 'shade_for_nonproduction_nonlast_types_column'
)



#6. Column sum <= 1

path_6 = model.addConstrs(
    (
    sum(paths[line, p1, p2] for p1 in PRODUCTS) <= 1 for p2 in PRODUCTS for line in LINES
    ),
    name = 'column_sum_less_or_equal_to_1'
)



#7 Row sum
  # Non last type
path_7_1 = model.addConstrs(
    (
     sum(paths[line, p1, p2] for p2 in PRODUCTS if p1 != p2) <= 1 for p1 in PRODUCTS  for line in LINES
    ),
    name = 'row_sum_less_or_equal_to_1'
)
  
  # Last type    
path_7_2_1 = model.addConstrs(
    (
      sum(paths[line, LAST_PRODUCTION[line], p2] for p2 in PRODUCTS if LAST_PRODUCTION[line] != p2) == 0 \
          for line in LINES if and_(sum(flags[line, p] for p in PRODUCTS if p != LAST_PRODUCTION[line]) ==0)
    ),
    name = 'row_sum_less_or_equal_to_0'
)
    

path_7_2_2 = model.addConstrs(
    (
      sum(paths[line, LAST_PRODUCTION[line], p2] for p2 in PRODUCTS if LAST_PRODUCTION[line] != p2) == 1 \
          for line in LINES if and_(sum(flags[line, p] for p in PRODUCTS if p != LAST_PRODUCTION[line]) >=1)
    ),
    name = 'row_sum_less_or_equal_to_1'
)



# There has to be way out from the last type 
path_8 = model.addConstrs(
    (
        sum(paths[line, p1, p2] for p2 in PRODUCTS) >= paths[line, LAST_PRODUCTION[line], p1] for p1 in PRODUCTS \
            for line in LINES if  p1 != LAST_PRODUCTION[line] 
    ),
    name = 'The 1st to product from last has to have its next type'
)






# Minimize the changeover cost
obj = sum(paths[line, p1, p2]*CHANGEOVER_COST[p1, p2] for p1 in PRODUCTS for p2 in PRODUCTS for line in LINES)

model.setObjective(obj, GRB.MINIMIZE)

model.setParam("MIPGap", 0.01)

model.optimize()


print('Time', time.time() - START_TIME)


#####################################################################################################
###############################   info extraction from model   ######################################
#####################################################################################################

SAVE_FOLDER = 'C:/daten/'

rows = LINES.copy()
columns = PRODUCTS.copy()

plan = pd.DataFrame(columns = columns, index = rows, data = 0)
indicator = pd.DataFrame(columns = columns, index = rows, data = 0)

plan.sort_index(inplace = True)
indicator.sort_index(inplace = True)

for line, product in hours.keys():
    #print(line, product, hours[line, product].x)
    if (abs(hours[line, product].x > 1e-6)):
        plan.loc[line, product] = np.round(hours[line, product].x,1)
        indicator.loc[line, product] = np.round(flags[line, product].x,1)

plan_transposed = plan.transpose().sort_index()
plan_transposed_2 = plan_transposed#plan_transposed[(plan_transposed.T != 0).any()]
plan_transposed_2.to_csv(SAVE_FOLDER + 'hours.csv')

indicator_transposed = indicator.transpose().sort_index()
indicator_transposed_2 = indicator_transposed[(indicator_transposed.T != 0).any()] 
indicator_transposed_2.to_csv(SAVE_FOLDER + 'flags.csv')

# Line #1 Path
rows = PRODUCTS.copy()
columns = PRODUCTS.copy()
line1 = pd.DataFrame(columns = columns, index = rows, data = 0)
for line, p1, p2 in paths.keys():
    if line == "L1":
        line1.loc[p1, p2] = np.round(paths[line, p1, p2].x,1)
    else:
        pass
line1.sort_index()
line1.to_csv(SAVE_FOLDER + "L1.csv")

# Line #2 Path
rows = PRODUCTS.copy()
columns = PRODUCTS.copy()
line2 = pd.DataFrame(columns = columns, index = rows, data = 0)
for line, p1, p2 in paths.keys():
    if line == "L2":
        line2.loc[p1, p2] = np.round(paths[line, p1, p2].x,1)
    else:
        pass
line2.sort_index(inplace = True)
line2.to_csv(SAVE_FOLDER + "L2.csv")
$\endgroup$
1
  • $\begingroup$ Maybe search for papers about "Parallel Machine Scheduling with Sequence-dependent Setups" and look at how they formulated things. $\endgroup$ Aug 6 '21 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.