SCIP求解生产切换问题

2023-12-24 10:33:10

本文参考的生产切换案例转载自 “ 运筹OR帷幄” 公众号，其文中使用gurobi求解此问题

本文使用免费开源SCIP求解器的python接口代码实现，最后与guribi求解的结果进行对比

案例

（一）案例一：生产切换

场景：

（1）二条产线 L1, L2，产能为 L1:24, L2:24

（2）四种产品：A1, A2, B1, B2, 需求量：A1: 14, A2: 10, B1:12, B2: 12

（3）四种产品切换的成本是

	A1	A2	B1	B2
A1	0	1	4	4
A2	1	0	4	4
B1	4	4	0	1
B2	4	4	1	0

（4）初始条件：上个班次最后的加工状态是 L1:A1, L2:A2

目标：

如何分配产品到产线上，在完成需求量的同时，切换成本最小

代码示例

import pandas as pd
import pyscipopt as opt

###############################   输入   ###################################

# 产品
PRODUCTS = ['A1','A2','B1','B2']

# 产线
LINES = ['L1', 'L2']

# 上一次生产中最后的产品
LAST_PRODUCTION = {
    'L1':'A1',
    'L2':'A2',
}

# 产品需求
DEMAND = {
    'A1':14,
    'A2':10,
    'B1':12,
    'B2':12,
}

# 切换成本
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 = {'L1': 24,
                 'L2': 24,}

# 时段数量
SLOTS = range(len(PRODUCTS))


def add_variable_by_idx_set(idx_set=None, var_name=None, var_type=None, lb=0, ub=None):
    variable = {}
    for idx in idx_set:
        variable[idx] = model.addVar(vtype=var_type, name=var_name + '_'.join(tuple(map(str,idx))), lb=lb, ub=ub)
    return variable

def process_data(SLOTS, LINES, PRODUCTS):

    list_tmp = []
    for i in SLOTS:
        list_tmp.append(i)

    products = pd.DataFrame(PRODUCTS).rename(columns={0: 'products'})
    slots = pd.DataFrame(list_tmp).rename(columns={0: 'slots'})
    lines = pd.DataFrame(LINES).rename(columns={0: 'lines'})

    products['cols'] = 1
    slots['cols'] = 1
    lines['cols'] = 1

    line_slots = pd.merge(lines, slots, on=['cols'], how='outer')
    line_products = pd.merge(lines, products, on=['cols'], how='outer')
    line_slots_products= pd.merge(line_slots, products, on=['cols'], how='outer')
    line_slots_products_products = pd.merge(line_slots_products, products, on=['cols'], how='outer', suffixes=['_star', '_end'])

    dict_line_slots = line_slots.set_index(['lines', 'slots'])['cols'].to_dict()
    dict_line_products = line_products.set_index(['lines', 'products'])['cols'].to_dict()
    dict_line_slots_products = line_slots_products.set_index(['lines', 'slots', 'products'])['cols'].to_dict()
    dict_line_slots_products_products = line_slots_products_products.set_index(['lines', 'slots', 'products_star', 'products_end'])['cols'].to_dict()

    return dict_line_slots, dict_line_products, dict_line_slots_products, dict_line_slots_products_products, line_slots_products

###############################   预处理数据   ###################################
dict_line_slots, dict_line_products, dict_line_slots_products, dict_line_slots_products_products, line_slots_products = process_data(
    SLOTS, LINES, PRODUCTS)

model = opt.Model()
M = 100000
B = 0.00001

# 变量：每个产线每个产品在每个时段的加工数量
quantity = add_variable_by_idx_set(idx_set=dict_line_slots_products.keys(), var_name='qty_', var_type='I')

# 变量：根据加工数量来判断每个产线的每个产品的每个时段是否被占用
isBusy = add_variable_by_idx_set(idx_set=dict_line_slots_products.keys(), var_name="isBusy_", var_type = 'B')

# 变量：每个产线每个时段是否被任何一个产品占用
slotBusy = add_variable_by_idx_set(idx_set=dict_line_slots, var_name="slotBusy_",  var_type = 'B')
slotBusy_sum = add_variable_by_idx_set(idx_set=dict_line_slots, var_name="slotBusy_sum_",  var_type = 'B')
slotBusy_b = add_variable_by_idx_set(idx_set=dict_line_slots, var_name="slotBusy_b_",  var_type = 'B')

#变量：每个产线每个时段从上时段产品到本时段产品的切换
changeOver = add_variable_by_idx_set(idx_set=dict_line_slots_products_products, var_type='B', var_name="changeOver_")

# 产品的实际生产
actual_prod = add_variable_by_idx_set(idx_set=DEMAND, var_type='I', var_name='d_')
line_capacity = add_variable_by_idx_set(idx_set=LINE_CAPACITY, var_type='I', var_name='line_cap_')
one_product_per_slot = add_variable_by_idx_set(idx_set=dict_line_slots, var_type='I', var_name='One_Product_Per_Slot_')

# 1. 约束 满足需求
for product, demand in DEMAND.items():
    model.addCons(opt.quicksum(quantity[line, slot, product] for line in LINES for slot in SLOTS) == demand)

# 2.不能超过产能
for line, line_capacity in LINE_CAPACITY.items():
    model.addCons(opt.quicksum(quantity[line, slot, product] for slot in SLOTS for product in PRODUCTS) <= line_capacity)

# 3. isBusy = sign(quantity)
for idx in dict_line_slots_products.keys():
    model.addCons(quantity[idx] >= isBusy[idx])
    model.addCons(quantity[idx] <= M * isBusy[idx])

#4. 每个产线的每个时段只能允许最多一个产品
for line_slot_idx in dict_line_slots.keys():
    line, slot = line_slot_idx
    model.addCons(opt.quicksum(isBusy[line, slot, product] for product in PRODUCTS) <= 1)

#5. 每个产线上每个产品只能出现在最多一个时段里
for line_product_idx in dict_line_products:
    line, product = line_product_idx
    model.addCons(opt.quicksum(isBusy[line, slot, product] for slot in SLOTS) <= 1)

#6. 统计每个时段被占用情况，不允许出现前面时段没有生产，后面时段有生产的情况
for line, slot in dict_line_slots:
    if slot != 0:
        model.addCons(slotBusy[line, slot-1] >= slotBusy[line, slot])

for line, slot in dict_line_slots:
    # slotBusy = max_([isBusy[line,n,product] for product in PRODUCTS])
    model.addCons(slotBusy_sum[line, slot] == opt.quicksum(isBusy[line, slot, product] for product in PRODUCTS))
    model.addCons(slotBusy[line, slot] >= slotBusy_sum[line, slot])
    model.addCons(slotBusy[line, slot] <= M * slotBusy_sum[line, slot])

#7. 统计每个时段的切换情况
# SLOTS[0:0]
for line, product in dict_line_products:
    if product == LAST_PRODUCTION[line]:
        model.addCons(changeOver[line, 0, LAST_PRODUCTION[line], product] == 0)
    else:
        model.addCons(changeOver[line, 0,  LAST_PRODUCTION[line], product] == isBusy[line, 0, product])

# SLOTS[1:]
for line, slot, product_1, product_2 in dict_line_slots_products_products:
    if slot != 0:
        if product_1 == product_2:
            model.addCons(changeOver[line, slot, product_1, product_2] == 0)
        else:
            isBusy_tmp = isBusy[line, slot-1, product_1] + isBusy[line, slot, product_2] - 2 + B
            and_isBusy = model.addVar(vtype='B', name='and_isBusy')
            model.addCons(isBusy_tmp <= and_isBusy * M)
            model.addCons(and_isBusy * M <= M + isBusy_tmp - B)

            model.addCons(changeOver[line, slot, product_1, product_2] == and_isBusy)

model.setObjective(opt.quicksum(changeOver[line, slot, product_1, product_2] * CHANGEOVER_COST[product_1, product_2]
                                for line, slot, product_1, product_2 in dict_line_slots_products_products))
model.setMinimize()
model.optimize()


print('\n\n###############################   输出结果   ######################################\n')
print('总切换成本：'+ '%3d' % model.getObjVal())
print('生产计划：')
q_r = pd.DataFrame(index=line_slots_products.set_index(['lines', 'slots', 'products']).index.unique())
q_r['qty'] = q_r.index.map(lambda x: model.getVal(quantity[x]))
q_r = q_r.loc[q_r['qty'] > 0].reset_index()
print(q_r)

结果对比

gurobi求解结果
scip求解结果

结论：从结果中看出，两者都求解出了可行解，其中L2生产的顺序与gurobi的结果不一致，原因是三者切换的成本相等。

码农公寓

案例

代码示例

结果对比

相关文章