板取り計画

solution.py

import matplotlib.pyplot as plt
import matplotlib.patches as patches

class Plane:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.spaces = [(0, 0, width, height)]
        self.used = []

    def plot(self, ratio=(1, 1), figsize=(1,1)):
        fig, ax = plt.subplots(figsize=figsize)
        p = patches.Rectangle(xy=(0,0), width=self.width*ratio[0], height=self.height*ratio[1], fc='w', ec='b')
        ax.add_patch(p)
        for u in self.used:
           p = patches.Rectangle(xy=(u[0]*ratio[0],u[1]*ratio[1]), width=u[2]*ratio[0], height=u[3]*ratio[1], fc='gray', ec='b')
           ax.add_patch(p)
        ax.set_xlim(0, self.width*ratio[0])
        ax.set_ylim(0, self.height*ratio[1])
        ax.invert_yaxis()
        plt.show()

    def envelope_width(self, used):
        """
        新たな使用領域を加えた使用領域幅
        """
        return max([p[0]+p[2] for p in self.used+[used]])
    
    def envelope_height(self, used):
        """
        新たな使用領域を加えた使用領域高さ
        """
        return max([p[1]+p[3] for p in self.used+[used]])

    def defective_x(self, used=None):
        """
        Y軸方向に切り詰めたときのX軸方向の総空き面積
        """
        u = [used] if used else []
        area = self.width * self.envelope_height(used if used else [0,0,0,0])
        for p in self.used+u:
            area -= p[2] * p[3]
        return area

    def defective_y(self, used=None):
        """
        X軸方向に切り詰めたときのY軸方向総空き面積
        """
        u = [used] if used else []
        area = self.envelope_width(used if used else [0,0,0,0]) * self.height
        for p in self.used+u:
            area -= p[2] * p[3]
        return area

    def used_area(self):
        """
        総使用領域
        """
        return sum([p[2] * p[3] for p in self.used])

    def use_space(self, width, height, space_indices=None):
        """
        空き領域を矩形で埋める
        return: 使用した領域番号, 使用領域, 追加空き領域, 探索済み最左領域幅, 探索済み領域最上高さ
        """
        if space_indices is None:
            space_indices = list(range(len(self.spaces)))
        use = -1
        min_x = self.width
        lw = 0
        min_y = self.height
        th = 0
        used = None
        frees = []
        # 優先順に空き領域を探索
        for i in space_indices:
            x, y, w, h = self.spaces[i]
            # 配置可能の場合
            if w >= width and h >= height:
                use = i
                free_w = w - width
                free_h = h - height
                # 新しい使用領域
                used = (x, y, width, height)
                # 配置後の隙間から空き領域を計算
                if free_w > 0 and free_h == 0:
                    frees.append((x+width, y, free_w, h))
                elif free_w > 0 and free_h > 0:
                    frees.append((x+width, y, free_w, h))
                    frees.append((x, y+height, width, free_h))
                else:
                    frees.append((x, y+height, w, free_h))
                break
            else: # 探索済み最左・上領域幅・高さをそれぞれ求める
                if min_x > x:
                    min_x = x
                    lw = w
                if min_y > y:
                    min_y = y
                    th = h
        return use, used, frees, lw, th

    def use_bottom(self, width, height):
        """
        左側に詰めて空き領域を矩形で埋める = 下側を優先して埋める
        """
        indices = list(range(len(self.spaces)))
        indices.sort(key=lambda i: self.spaces[i][0])
        return self.use_space(width, height, space_indices=indices)

    def use_right(self, width, height):
        """
        上側に詰めて空き領域を矩形で埋める = 右側を優先して埋める
        """
        indices = list(range(len(self.spaces)))
        indices.sort(key=lambda i: self.spaces[i][1])
        return self.use_space(width, height, space_indices=indices)

class Order:
    def __init__(self, width, length, max_divide, tolerance):
        self.width = width
        self.length = length
        self.div_count = max_divide
        self.tolerance = tolerance

    def divide(self, length):
        """
        オーダーを指定した長さで分割する
        """
        if self.div_count <= 0:
            raise NameError('Reached the maximum division count')
        if length >= self.length:
            raise NameError('Exceeded dividable length')
        return Order(self.width, length, 0, 0), Order(self.width, self.length-length, self.div_count-1, self.tolerance)

def evaluation(time_for_making, time_for_blade, unit_value, area, defective, blade_count):
    """
    時間当たりの利益を評価

    time_for_making: コイル当たりの生産時間 a
    time_for_blade: 刃替え時間 b
    unit_value: 単位面積当たりの鉄板の価格 c
    area: オーダー総面積 d
    defective: 不良面積 e
    blade_count: 刃替え回数 f

    return: (c*(d-e))/(a+f*b)
    """
    return (unit_value*(area-defective))/(time_for_making+blade_count*time_for_blade)


def planning(coil_w, coil_len, orders, max_divide=15, evaluation=lambda a,b,c:(a-b)/(c+1)):
    """
    板取り計画

    coil_w: コイル幅
    coil_len: コイル長さ
    orders: オーダーリスト
    max_divide: 最大分割可能回数
    evaluation: 評価関数(オーダー総面積, 不良面積, 刃替え回数)

    return: 評価値, 計画後コイル平面リスト
    """
    # 使用するコイル平面リスト
    planes = [Plane(coil_len, coil_w)]
    # オーダーインスタンスリスト
    orders = [Order(order[0], order[1], max_divide, 0) if len(order) == 2
            else Order(order[0], order[1], max_divide, order[2]) for order in orders]
    # 幅が大きいオーダーから順に処理する
    orders.sort(key=lambda order: order.width)
    # オーダー総面積
    ordered_area = sum([o.width*o.length for o in orders])
    # 刃交換回数
    sum_divnum = 0

    # 全てのオーダーを処理するまで繰り返し
    while len(orders) > 0:
        p = planes[-1]
        o = orders.pop()
        if o.width > coil_w:
            raise NameError('Order exceeded coil length')
        # 現在のオーダーの配置計画
        states = next_states(p, o, ordered_area, evaluation)
        # 計画不可能だった場合(コイル平面に収まらない)、コイルを増やして再計画
        if len(orders) > 0 and len(states) == 0:
            print("Cannot place! Make a new plane.")
            planes.append(Plane(coil_len, coil_w))
            continue
        # 評価値の高い計画を採用
        states.sort(key=lambda s: s[0], reverse=True)
        # 空き領域高さがオーダーの倍以上存在する場合、分割を検討する
        if len(orders) == 0 and o.div_count > 0:
            div_num = 0
            defective = ordered_area
            # 全ての空き領域に対して、分割配置後の最小不良面積とその分割回数を求める
            for free in p.spaces:
                if free[3] >= o.width:
                    _defective = (free[3] % o.width) * free[2]
                    if defective > _defective:
                        defective = _defective
                        div_num = int(max(div_num, min(o.div_count, free[3]//o.width)))
            if div_num > 0:
                # 分割配置の評価値が事前の計画以上の場合、オーダーを分割して再計画
                if len(states) > 0:
                    ev = states[0][0]
                else:
                    ev = -1e9
                if evaluation(ordered_area, defective, div_num) > ev:
                    sum_divnum += div_num
                    orders.extend([Order(o.width, int(o.length/div_num), 0, o.tolerance/div_num)] * div_num)
                    continue
        ev, use, used, frees, div = states[0]
        # コイル平面を更新
        if div:
            orders.append(div)
            sum_divnum += 1
        del p.spaces[use]
        p.used.append(used)
        p.spaces.extend(frees)

    # 最終的な評価値とコイル平面を返す
    sum_defective = sum([p.defective_y() for p in planes])
    return evaluation(ordered_area, sum_defective, sum_divnum), planes

def next_states(plane, order, ordered_area, evaluation):
    """
    コイル平面に対して1つのオーダーの配置を計画する

    plane: コイル平面
    order: オーダーインスタンス
    ordered_area: オーダー総面積
    evaluation: 評価関数

    return [(評価値, 使用する領域番号, 使用領域, 追加空き領域, 分割残りオーダー)]
    """
    states = []
    use, used, frees, lw, th = plane.use_bottom(order.length, order.width)
    # 直接配置可能な場合
    if use >= 0:
        defective_area = plane.defective_y(used)
        e = evaluation(ordered_area, defective_area, 0)
        states.append((e, use, used, frees, None))
    # 左側で分割配置可能な領域が存在する場合
    if 0 < lw and lw < order.length and order.div_count > 0:
        order_0, order_1 = order.divide(lw)
        use, used, frees, lw, lh = plane.use_bottom(order_0.length, order_0.width)
        if use >= 0:
            defective_area = plane.defective_y(used)
            e = evaluation(ordered_area, defective_area, 1)
            states.append((e, use, used, frees, order_1))
    return states

def print_result(ev, planes):
    #  pass
    print("評価値:", ev, "\n", list(map(lambda p: p.used, planes)))
    for p in planes:
        p.plot(ratio=(1000,1), figsize=(10,3))

def test():
    ev = lambda a, b, c: evaluation(10, 1, 1, a, b, c)
    ex1 = {
            "coil_w": 1000,
            "coil_len": 300,
            "orders": [
                (400, 100),
                (300, 100),
                (200, 100),
                (100, 100)
                ]
            }
    print_result(*planning(**ex1, evaluation=ev))
    ex2 = {
            "coil_w": 1000,
            "coil_len": 300,
            "orders": [
                (400, 100),
                (200, 200),
                (100, 200)
                ]
            }
    print_result(*planning(**ex2, evaluation=ev))
    ex3 = {
            "coil_w": 1000,
            "coil_len": 300,
            "orders": [
                (400, 100),
                (300, 100),
                (200, 100),
                ]
            }
    print_result(*planning(**ex3, evaluation=ev))
    ex4 = {
            "coil_w": 1000,
            "coil_len": 300,
            "orders": [
                (500, 100, 20),
                (250, 250, 10),
                ]
            }
    print_result(*planning(**ex4, evaluation=ev))

    ex5 = {
            "coil_w": 1000,
            "coil_len": 300,
            "orders": [
                (100, 1000),
                ]
            }
    print_result(*planning(**ex5, evaluation=ev))

    ex6 = {
            "coil_w": 1000,
            "coil_len": 300,
            "orders": [
                (600, 100),
                (500, 100),
                (400, 200),
                (300, 150),
                (200, 50),
                ]
            }
    print_result(*planning(**ex6, evaluation=ev))

    ex7 = {
            "coil_w": 1000,
            "coil_len": 300,
            "orders": [
                (600, 200),
                (500, 200),
                ]
            }
    print_result(*planning(**ex7, evaluation=ev))

if __name__ == '__main__':
    test()
    #  import time
    #  import numpy as np
    #  results = []
    #  for i in range(10000):
    #      t1 = time.time()
    #      test()
    #      t2 = time.time()
    #      elapsed = t2-t1
    #      results.append(elapsed)
    #  print(np.mean(results), np.var(results))