Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Solution unable to converge for Assignment with Task Sizes #1578

Closed
KungFuPandey opened this issue Sep 13, 2019 · 13 comments
Closed

Solution unable to converge for Assignment with Task Sizes #1578

KungFuPandey opened this issue Sep 13, 2019 · 13 comments
Assignees
@lperron
Milestone
v8.0

Comments

@KungFuPandey
Copy link

KungFuPandey commented Sep 13, 2019 •
edited

Hi,

I tried to elaborate on the Assignment with Task Sizes by adding a multi-dimensional "size" and "total_size_max" .

The solution seems to decide to allocate everything to 1 worker only despite the fact that others are available. The result when run allocates everything to worker(machine 18).

Sample output :

Machine 18 is assigned to produce Component 0 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 1 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 2 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 3 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 4 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 5 with minimum Cycle_Time = 10000000

Attaching the code as a txt file here as it doesnt supports a py extension.

test6.txt

I took this from the sample example and tweaked input data according to need. Can you help resolve ?
@lperron
Copy link
Collaborator

lperron commented Sep 13, 2019 via email

@KungFuPandey
Copy link
Author

Total_size_max is now a multi-dim array to meet the need of variable sized constraint for each machine(worker). I have just divided each "cost" by the max value so that i get a worker(machine) level max limit.

Below is the output of the same :
array([[324173, 0, 0, ..., 0, 0, 0], [ 0, 0, 0, ..., 0, 0, 0], [ 0, 0, 0, ..., 0, 0, 0], ..., [ 0, 120153, 0, ..., 0, 0, 0], [ 0, 306538, 0, ..., 0, 0, 0], [ 0, 382508, 0, ..., 0, 0, 0]])

@lperron
Copy link
Collaborator

lperron commented Sep 13, 2019 via email

@KungFuPandey
Copy link
Author

KungFuPandey commented Sep 13, 2019 •
edited

i understand, but then there are possibilities where the solution should be able to allocate it correctly.

The similar code here works (having no 1s ofcourse helped it) for lesser data-set but doesnt works for larger (and sparse) dataset.
IM_test6 - Copy.txt

@lperron
Copy link
Collaborator

lperron commented Sep 13, 2019 via email

@KungFuPandey
Copy link
Author

alright,
the reason why there are many 0s there is because i had to add in a large number(10000000) in COST where a machine cannot make a component.

is there a way to work-around this?

@lperron
Copy link
Collaborator

lperron commented Sep 13, 2019 via email

@KungFuPandey
Copy link
Author

thanks, your approach sounds great!

so I will be replacing the entries with -1 in cost
and
how would the check to ignore -1s be used in the below code ?

model.Minimize(sum([np.dot(x_row, cost_row) for (x_row, cost_row) in zip(x, costlist)]))
`

sorry i'm totally new (but eager to learn) to or-tools if this is a simple ask.

@lperron
Copy link
Collaborator

lperron commented Sep 13, 2019 via email

@lperron lperron closed this as completed Sep 14, 2019
@lperron
Copy link
Collaborator

lperron commented Sep 14, 2019 via email

@KungFuPandey
Copy link
Author

KungFuPandey commented Sep 19, 2019 •
edited

Hi Laurent,

Thanks for the comprehensive detailing on the above, this really helps!

I wanted to know how/where do you get the details of the optimization (as mentioned in above comment where variables , riles and cpsolver details are mentioned). The information from OR output stack may help me to better understand how it optimized to a solution.

How did you reach to a conclusion of choosing 8 num_search_workers only ?

also - this one is near perfect(if not perfect already) - to take care of the scenario when the demand > availability on the BEST machine , but could be met if divided to other possible 2ndbest/3rd best.. machines. I just tried this and it works absolutely perfect.
This really helps!

@KungFuPandey
Copy link
Author

KungFuPandey commented Sep 20, 2019 •
edited

I see there is a minor bug in this approach , if the demand for a component is increased to a large value (lets say 324000) , and the cycle_time to produce that component is just over an integer rounded value (lets say 8.0193 ), then the total hours to make it will exceed (2598253 hrs) over the available hours (2592000).
it is because we are rounding off the cost from 8.019 to 8 in order to get the optimization done.

how can we address this issue ?
An example to show this is below :

# -*- coding: utf-8 -*-
from __future__ import print_function

from ortools.sat.python import cp_model
import time
import numpy as np
import pandas as pd


class fetch_data: 
    def __init__(self):
        # set COST
        self.cost = [[-1,7.995722268,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [6.764712938,-1,6.64179678,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,26.10110138,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,29.63946277,27.72432227,24.79202174,29.4907994,-1,-1],
            [-1,-1,-1,-1,-1,6.271052178,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,8.213437897,-1,-1,4.372568825,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,6.282863934,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,15.49746661,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,14.36944353,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,14.95278777,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,13.33333333,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,6.194286893,-1,14.56521739,-1,17.57157641,-1,-1,-1,-1,-1,-1],
            [-1,8.076237035,-1,-1,4.400797794,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,8.019304639,-1,-1,4.496583613,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,3.778990587,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,11.51228733,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,11.06301248,-1,4.492667454,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,5.512785364,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1.780837358],
            [-1,-1,-1,-1,-1,-1,-1,-1,7.755011055,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,29.69460764,25.45422456,32.00169225,-1,-1],
            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,27.13193117,28.19319991,26.59704717,-1,-1],
            [-1,-1,-1,21.5723175,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,8.455696203,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
            [-1,-1,-1,6.776314217,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
           ]
        
        # set DEMAND
        #self.demand = [1087,500000,194,1544,1544,1544,1544,1087,263,194,1087,179,84,194,1544,3088] #263 for component-1   
        self.demand = [ ("a",1087),	("b",500000),	("c",194),	("d",1544),	("e",1544),	("f",1544),	("g",1544),	("h",1087),	("i",263),	("j",194),	("k",1087),	("l",179),	("m",84),	("n",194),	("o",1544),	("p",3088)]
        
        # set AVAILABLE HOURS
        #self.available_hrs = [2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000]
        self.available_hrs = [ ('IMM01',2592000) , ('IMM02',2592000) , ('IMM08',2592000) , ('IMM09',2592000)  , ('21',2592000) ,  ('31',2592000) , ('32',2592000) , ('34',2592000) , ('35',2592000)  , ('38',2592000) , ('40',2592000) , ('42',2592000)  , ('43',2592000) , ('44',2592000)  , ('45',2592000) , ('46',2592000) , ('47',2592000) , ('49',2592000) , ('56',2592000) , ('58',2592000) , ('L06',2592000) , ('L07',2592000) , ('L12',2592000) , ('L18',2592000) , ('L33',2592000) ]


def get_data():
    return fetch_data()

    

def IM_solution(c, d, a):
    model = cp_model.CpModel()

    start = time.time()
    
#    cost = [[-1,7.995722268,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [6.764712938,-1,6.64179678,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,26.10110138,-1,-1,-1],
#            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,29.63946277,27.72432227,24.79202174,29.4907994,-1,-1],
#            [-1,-1,-1,-1,-1,6.271052178,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,8.213437897,-1,-1,4.372568825,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,6.282863934,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,-1,-1,-1,-1,15.49746661,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,-1,-1,-1,-1,14.36944353,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,-1,-1,-1,-1,14.95278777,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,-1,-1,13.33333333,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,6.194286893,-1,14.56521739,-1,17.57157641,-1,-1,-1,-1,-1,-1],
#            [-1,8.076237035,-1,-1,4.400797794,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,8.019304639,-1,-1,4.496583613,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,-1,3.778990587,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,11.51228733,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,11.06301248,-1,4.492667454,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,5.512785364,-1],
#            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1.780837358],
#            [-1,-1,-1,-1,-1,-1,-1,-1,7.755011055,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,29.69460764,25.45422456,32.00169225,-1,-1],
#            [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,27.13193117,28.19319991,26.59704717,-1,-1],
#            [-1,-1,-1,21.5723175,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,8.455696203,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#            [-1,-1,-1,6.776314217,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
#           ]

    cost = c
    int_cost = [[int(round(x)) for x in line] for line in cost]

    # demand for each component
    #demand = [1087,500000,194,1544,1544,1544,1544,1087,263,194,1087,179,84,194,1544,3088] #263 for component-1
    demand = d

    # total available hours
    #available_hrs = [2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000,2592000]
    available_hrs = a

    num_workers = len(int_cost)
    num_tasks = len(int_cost[1])
    print('num_workers =', num_workers, ', num_tasks =', num_tasks)

    # Variables
    x = [[
        0 if int_cost[i][j] == -1 else model.NewIntVar(
            0, demand[j], 'x[%i,%i]' % (i, j)) for j in range(num_tasks)
    ] for i in range(num_workers)]

    # Constraints

    # For each component, demand is met.
    for j in range(num_tasks):
        model.Add(
            sum(x[i][j] for i in range(num_workers)
                if int_cost[i][j] >= 0) == demand[j])

    # Total worked hours for each machine is at most available_hrs.
    for i in range(num_workers):
        model.Add(
            sum(x[i][j] * int_cost[i][j]
                for j in range(num_tasks)) < available_hrs[i])

    # Objective: minimize worked hours.
    model.Minimize(
        sum(x[i][j] * int_cost[i][j] for i in range(num_workers)
            for j in range(num_tasks) if int_cost[i][j] != -1))

    # Solve.
    solver = cp_model.CpSolver()
    solver.parameters.log_search_progress = True
    solver.parameters.num_search_workers = 8
    status = solver.Solve(model)

    # Print solution.
    if status == cp_model.OPTIMAL:
        print('Minimum cost = %i' % solver.ObjectiveValue())
        print()
        lst_res = []
        for i in range(num_workers):

            for j in range(num_tasks):
                qty = 0 if cost[i][j] == -1 else solver.Value(x[i][j])
                if qty > 0:
                    print('Machine ', i, ' is assigned to produce', qty,
                          'of Component ', j, ' with minimum Cycle_Time = ',
                          cost[i][j])
                    # add each row to a list
                    lst = [i,j,cost[i][j],qty]
                    #append each list to final list
                    lst_res.append(lst)
        print()
        end = time.time()
        print("Time = ", round(end - start, 4), "seconds")
    
    df_res = pd.DataFrame(data = lst_res , columns = ['Machine#', 'Component#' , 'Cycle_Time' , 'Demand_met']) 
    #print(df_res)
    return df_res

if __name__ == '__main__':
    data = get_data()
    # get Cost
    c = data.cost
    # get demand
    d1 = data.demand
    d1_dict = dict(d1)
    d = list(d1_dict.values())
    df_d = pd.DataFrame( data=d1 , columns = ['Component' , 'Demand'] )
    df_d.reset_index(inplace = True)
    df_d = df_d.rename(columns = {"index": "Component#"})
    # get available hours
    a1 = data.available_hrs
    a1_dict = dict(a1)
    a = list(a1_dict.values())
    df_a = pd.DataFrame( data=a1 , columns = ['Machine' , 'Available_hours'] )
    df_a.reset_index(inplace = True)
    df_a = df_a.rename(columns = {"index": "Machine#"})
    #print("COST :")
    #print(c)
    #print("DEMAND :")
    #print(d)
    #print("AVAILABLE HOURS :")
    #print(a)
    
    # Call IM optimization solution 
    df_IMres = IM_solution(c,d,a)
    #print(df_IMres)
    
    #combine result with demand and avaiable hrs to calculate metrics
    df_merged1 = pd.merge(df_IMres, df_d, how = 'left', on =['Component#'])
    df_merged1 = pd.merge(df_merged1, df_a, how = 'left', on =['Machine#'])
    df_merged1['Max_comp_possible'] = df_merged1.apply(lambda row: (row.Available_hours / row.Cycle_Time ), axis = 1) 
    df_merged1['%Demand_met'] = df_merged1.apply(lambda row: (row.Demand_met / row.Demand ), axis = 1) 
    df_merged1['Used_hours'] =  df_merged1.apply(lambda row: (row.Cycle_Time * row.Demand_met ), axis = 1) 
    df_merged1['%Utilization'] =  df_merged1.apply(lambda row: (row.Used_hours / row.Available_hours ), axis = 1) 
    #df_merge1.to_csv('temp1.csv')
    print(df_merged1)

@lperron
Copy link
Collaborator

lperron commented Sep 20, 2019 via email

@Mizux Mizux added this to the v8.0 milestone Feb 12, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@lperron lperron

Labels
None yet
Projects
None yet
Milestone
v8.0
Development

No branches or pull requests
3 participants
@Mizux @KungFuPandey @lperron