Topic
  • 10 replies
  • Latest Post - ‏2013-03-25T20:11:19Z by SystemAdmin
SystemAdmin
SystemAdmin
378 Posts

Pinned topic Line Balancing Problem - error in objective function

‏2013-02-28T01:26:48Z |
Hey,

I am fairly new to CPLEX. I need to solve an assembly line balancing problem where the objective function is defined as the mean absolute deviation of the work output of different tasks. These tasks are subject to some precedence constraints and only certain workers have skills to perform certain tasks. In addition, each worker has an efficiency associated with performing a certain task.

To calculate the mean absolute deviation, I need to calculate the ((abs(output of task[i] - average output of all tasks))/total number of tasks) summed over all tasks

The objective function that I have written returns a series of errors: "CP cannot extract expression"

I am not sure if the error is being caused by using a combination of indexed decision expressions and non indexed decision expressions in the objective function. I don't know how to rewrite it to make it work. Any help would be really appreciated.

I have attached the mod file and the dat file.

My code is as follows:

using CP;

int nTasks = ...;
int nStations = ...;
int nWorkers = ...;

int CycleTime = ...;

range rTasks = 1..nTasks;
range rStations = 1..nStations;
range rWorkers = 1..nWorkers;

{string} Tasks = ...;
{string} Stations = ...;
{string} Workers = ...;

int OperationTimesTasks = ...;
int TimeAvailableWorkers = ...;

tuple Skill
{
string Worker;
string Task;
float Efficiency;
};
{Skill} Skills = ...;

tuple Precedence {
string pre;
string post;
};
{Precedence} Precedences = ...;

dvar interval dvTasks t in Tasks in 0..CycleTime size OperationTimes[t];
dvar interval dvWorkersToTasks s in Skills optional;

//Work output of each task
dexpr float TheoreticalProductiont in Taskss in Skills =
presenceOf(dvWorkersToTasks[s])*(TimeAvailable[t]/(OperationTimes[t]/s.Efficiency));

//Total work output
dexpr float TotalTheoreticalProduction = sum(t in Tasks, s in Skills)
TheoreticalProduction[t][s];

//Average work output
dexpr float AvgTheoreticalProduction =
TotalTheoreticalProduction/nTasks;

//Minimize Mean Absolute Deviation

minimize sum(t in Tasks, s in Skills)
abs(TheoreticalProduction[t][s] - AvgTheoreticalProduction)/nTasks;

subject to
{
forall(p in Precedences)
endBeforeStart(dvTaskshttp://p.pre, dvTaskshttp://p.post);
forall(t in Tasks)
alternative(dvTasks[t], all(s in Skills: s.Task==t) dvWorkersToTasks[s]);
forall(w in Workers)
noOverlap(all(s in Skills: s.Worker==w) dvWorkersToTasks[s]);
};
Updated on 2013-03-25T20:11:19Z at 2013-03-25T20:11:19Z by SystemAdmin
  • GGR
    GGR
    35 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-02-28T17:57:48Z  
    Hi

    The problem comes from an indexation error

    
    dexpr 
    
    float TheoreticalProduction[t in Tasks][s in Skills] = presenceOf(dvWorkersToTasks[s])*(TimeAvailable[t]/(OperationTimes[t]/s.Efficiency));
    


    the TimeAvailable array is indexed by the Workers tuple set but not the Tasks tuple set as in the expression TheoreticalProduction.

    I do not know how to change this in the expression but I hope that helps.
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-03-01T05:49:53Z  
    • GGR
    • ‏2013-02-28T17:57:48Z
    Hi

    The problem comes from an indexation error

    <pre class="jive-pre"> dexpr float TheoreticalProduction[t in Tasks][s in Skills] = presenceOf(dvWorkersToTasks[s])*(TimeAvailable[t]/(OperationTimes[t]/s.Efficiency)); </pre>

    the TimeAvailable array is indexed by the Workers tuple set but not the Tasks tuple set as in the expression TheoreticalProduction.

    I do not know how to change this in the expression but I hope that helps.
    Thank you for your reply. I have rewritten the expression:

    dexpr float TheoreticalProductiont in Tasksw in Workerss in Skills =
    presenceOf(dvWorkersToTasks[s])*(TimeAvailable[w]/(OperationTimes[t]/s.Efficiency));
    I tried running it again. The code runs for about 45 min and gives me a solution which contains 3 indexes:
    TheoreticalProductionTasksWorkersSkills

    I just need TheoreticalProductionTasks. But I don't know how to create that variable because the formula that is used to calculate TheoreticalProduction requires values from TimeAvailableWorkers, dvWorkersToTasks and s.Efficiency.

    I need something like this:

    dexpr float TheoreticalProductiont in Tasks = (s in Skills, t in Tasks, w in Workers)
    presenceOf(dvWorkersToTasks[s])*(TimeAvailable[w]/(OperationTimes[t]/s.Efficiency));

    I know it requires a sum function to work but is there any way to write it without one?
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-03-01T14:42:23Z  
    Thank you for your reply. I have rewritten the expression:

    dexpr float TheoreticalProductiont in Tasksw in Workerss in Skills =
    presenceOf(dvWorkersToTasks[s])*(TimeAvailable[w]/(OperationTimes[t]/s.Efficiency));
    I tried running it again. The code runs for about 45 min and gives me a solution which contains 3 indexes:
    TheoreticalProductionTasksWorkersSkills

    I just need TheoreticalProductionTasks. But I don't know how to create that variable because the formula that is used to calculate TheoreticalProduction requires values from TimeAvailableWorkers, dvWorkersToTasks and s.Efficiency.

    I need something like this:

    dexpr float TheoreticalProductiont in Tasks = (s in Skills, t in Tasks, w in Workers)
    presenceOf(dvWorkersToTasks[s])*(TimeAvailable[w]/(OperationTimes[t]/s.Efficiency));

    I know it requires a sum function to work but is there any way to write it without one?
    I have been able to figure out the problem.

    I have one more question. I am trying to include partial worker assignment in my model. Is it possible to write constraints to obtain the following solutions in CPLEX:

    Scenario 1:
    I have 3 workers and 3 tasks. I want to know if the following solution is possible:
    Worker 1 is assigned to task A 50% of the time and task B 50% of the time.
    Worker 2 is assigned to task B 50% of the time and task C 50% of the time.
    Worker 3 is assigned to task C 50% of the time and task A 50% of the time.

    Scenario 2:
    I have 3 workers and 3 tasks. I want to know if the following solution is possible:
    Worker 1 is assigned to task A 30% of the time, task B 50% of the time and task C 20% of the time.
    Worker 2 is assigned to task A 40% of the time, task B 20% of the time and task C 40% of the time.
    Worker 3 is assigned to task A 30% of the time, task B 30% of the time and task C 40% of the time.

    Scenario 3:
    I have 4 workers and 3 tasks. I want to know if the following solution is possible: (Workers are allowed to be idle for some percentage of time)
    Worker 1 is assigned to task A 30% of the time, task B 10% of the time and task C 20% of the time.
    Worker 2 is assigned to task A 20% of the time, task B 10% of the time and task C 40% of the time.
    Worker 3 is assigned to task A 20% of the time, task B 10% of the time and task C 40% of the time.
    Worker 4 is assigned to task A 30% of the time and task B 70% of the time

    As far as I know, the 'presenceOf' function returns a 0 or 1 value depending on whether a variable is present in the solution. Is there function which can return a value between 0 and 1?

    My code is as follows:

    using CP;

    int nTasks = ...;
    int nStations = ...;
    int nWorkers = ...;

    int CycleTime = ...;

    range rTasks = 1..nTasks;
    range rStations = 1..nStations;
    range rWorkers = 1..nWorkers;

    {string} Tasks = ...;
    {string} Stations = ...;
    {string} Workers = ...;

    int OperationTimesTasks = ...;
    int TimeAvailableWorkers = ...;

    tuple Skill
    {
    string Worker;
    string Task;
    float Efficiency;
    };
    {Skill} Skills = ...;

    tuple Precedence {
    string pre;
    string post;
    };
    {Precedence} Precedences = ...;

    dvar interval dvTasks t in Tasks in 0..CycleTime size OperationTimes[t];
    dvar interval dvWorkersToTasks s in Skills optional;

    //Work output of each task
    dexpr float TheoreticalProductiont in Tasks=
    sum(s in Skills : s.Task == t, w in Workers: s.Worker == w)
    presenceOf(dvWorkersToTasks[s])*(TimeAvailable[w]/(OperationTimes[t]/s.Efficiency));

    //Total work output
    dexpr float TotalTheoreticalProduction = sum(t in Tasks)
    TheoreticalProduction[t];

    //Average work output
    dexpr float AvgTheoreticalProduction =
    TotalTheoreticalProduction/nTasks;

    execute
    {
    cp.param.FailLimit = 10000;
    }

    //Minimize Mean Absolute Deviation
    minimize sum(t in Tasks)
    abs(TheoreticalProduction[t] - AvgTheoreticalProduction)/nTasks;

    subject to
    {
    forall(p in Precedences)
    endBeforeStart(dvTaskshttp://p.pre, dvTaskshttp://p.post);
    forall(t in Tasks)
    alternative(dvTasks[t], all(s in Skills: s.Task==t) dvWorkersToTasks[s]);
    forall(w in Workers)
    noOverlap(all(s in Skills: s.Worker==w) dvWorkersToTasks[s]);

    };
    I have also attached the mod file.
  • GGR
    GGR
    35 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-03-01T15:37:30Z  
    Hi

    Each task executed by a worker even partially is an interval variable (let's call this an operation). I suppose the sharing of the tasks is the sharing of the processing time. In such a case the task is no more the alternative of the operation. So this part of the model must be rewritten.

    By the way, I am surprised of your notion of efficiency in your model. As for me the size of the operation should be normalized by the efficiency of the worker. Am I right?

    • An operation is an interval variable. I suggest to give bounds on the size of the operations
    • The sum of the sizes, weighted by the worker efficiency, of the operations of a task is the operationTimeTasks of your data. Caution, operation Time is an integer, the weighted sum a floating point. use a range constraint or a floor expression.
    • You must complete the model with temporal rules, precedence constraints or maximum number of operation executed simultaneously for a task by using a cumul expression.

    To check a solution, you simply state the corresponding constraint. E.g 50% of task by worker is a range constraint on the sizeOf expression of the operation.

    Hope that helps
    Hope that helps.
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-03-01T21:35:46Z  
    • GGR
    • ‏2013-03-01T15:37:30Z
    Hi

    Each task executed by a worker even partially is an interval variable (let's call this an operation). I suppose the sharing of the tasks is the sharing of the processing time. In such a case the task is no more the alternative of the operation. So this part of the model must be rewritten.

    By the way, I am surprised of your notion of efficiency in your model. As for me the size of the operation should be normalized by the efficiency of the worker. Am I right?

    • An operation is an interval variable. I suggest to give bounds on the size of the operations
    • The sum of the sizes, weighted by the worker efficiency, of the operations of a task is the operationTimeTasks of your data. Caution, operation Time is an integer, the weighted sum a floating point. use a range constraint or a floor expression.
    • You must complete the model with temporal rules, precedence constraints or maximum number of operation executed simultaneously for a task by using a cumul expression.

    To check a solution, you simply state the corresponding constraint. E.g 50% of task by worker is a range constraint on the sizeOf expression of the operation.

    Hope that helps
    Hope that helps.
    Thank you so much. Yes you are right, the operation time should be normalized by the efficiency of the worker. I will rewrite the model and incorporate the changes you have suggested.
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-03-22T00:04:53Z  
    The value of the objective function that is generated by the CPLEX engine is different from the value that is calculated by a decision expression.
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-03-22T00:14:22Z  
    The value of the objective function that is generated by the CPLEX engine is different from the value that is calculated by a decision expression.
    Hey GGR,

    I have another question. I was able to include the partial assignments and normalized efficiency. But the problem now is that when I run the code, the solution that is shown when I click on the solutions tab is 89.216. I have used a decision expression to calculate the mean absolute deviation and its value is actually 2.656.

    The expression I have used is: "minimize MeanAbsoluteDeviation" and the value for MeanAbsoluteDeviation has been calculated using other decision expressions. I don't understand why the solution in the solution tab is not 2.656 considering that uses the same decision expressions.

    I have attached the dat file and my code is shown below.

    
    using CP; 
    
    int nTasks = ...; 
    
    int nWorkers = ...; 
    
    int nMachines = ...; 
    
    int Demand = ...; 
    
    int CycleTime = ...; 
    
    int nMaxTrips = ...; 
    {string
    } Tasks = ...; 
    {string
    } Workers = ...; 
    
    int TimeAvailableSystem = ...; 
    
    int TimeAvailable[Workers]= ...; 
    
    int StdOperationTimes[Tasks] = ...; tuple Skill 
    { string Worker; string Task; 
    
    float Efficiency; 
    }; 
    {Skill
    } Skills = ...; tuple PrecedenceS 
    { string Task; 
    {string
    } pre; 
    }; 
    {PrecedenceS
    } PrecedencesSet = ...; tuple PrecedencePP 
    { string pre; string post; 
    }; 
    {PrecedencePP
    } PrecedencesPrePost = ...; 
    
    float ActualOperationTimes[s in Skills] = sum(t in Tasks : t == s.Task) StdOperationTimes[t]/s.Efficiency; dvar 
    
    boolean dvB[Workers][Tasks]; dvar int+ dvPartial[Workers][Tasks]; dvar 
    
    int dvMachinesToTask[Tasks]; dvar interval dvTasks [t in Tasks] in 0..CycleTime; dvar interval dvWorkersToTasks [s in Skills] optional size ftoi(round(ActualOperationTimes[s])); 
    //Theoretical work output of each task dexpr 
    
    float TheoreticalProduction[t in Tasks]= sum(s in Skills : s.Task == t, w in Workers: s.Worker == w) (dvB[w][t]*dvPartial[w][t]/100)*dvMachinesToTask[t]*presenceOf(dvWorkersToTasks[s])*TimeAvailable[w]/ActualOperationTimes[s]; 
    //Actual work output of each task dexpr 
    
    float ActualProduction[t in Tasks] = minl (TheoreticalProduction[t], sum(p in PrecedencesSet : p.Task == t) min(r in p. pre) TheoreticalProduction[r]); 
    //Total work output dexpr 
    
    float TotalActualProduction = sum(t in Tasks) ActualProduction[t]; 
    //Average work output dexpr 
    
    float AvgActualProduction = TotalActualProduction/nTasks; 
    //AbsoluteDeviation dexpr 
    
    float AbsoluteDeviation[t in Tasks] = abs(ActualProduction[t] - AvgActualProduction); 
    //MeanAbsoluteDeviation dexpr 
    
    float MeanAbsoluteDeviation = (sum(t in Tasks) AbsoluteDeviation[t])/nTasks; execute 
    { cp.param.FailLimit = 10000; 
    } 
    //Minimize Mean Absolute Deviation minimize MeanAbsoluteDeviation; subject to 
    { forall(p in PrecedencesPrePost) endBeforeStart(dvTasks[p.pre], dvTasks[p.post]); forall(t in Tasks) alternative(dvTasks[t], all(s in Skills: s.Task==t) dvWorkersToTasks[s]); forall(w in Workers) noOverlap(all(s in Skills: s.Worker==w, t in Tasks : t == s.Task) dvWorkersToTasks[s]); forall(t in Tasks) dvMachinesToTask[t] >= 1; sum(t in Tasks) dvMachinesToTask[t] <= nMachines; ActualProduction[last(Tasks)] >= Demand; forall(w in Workers) sum(t in Tasks) dvPartial[w][t]==100; forall(w in Workers, t in Tasks) dvPartial[w][t] <= 100 * dvB[w][t]; forall(w in Workers, t in Tasks) dvPartial[w][t] >= 20 * dvB[w][t]; forall(w in Workers) sum(t in Tasks) dvB[w][t] <= nMaxTrips+1; 
    };
    
  • rdumeur
    rdumeur
    26 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-03-22T16:23:31Z  
    Hey GGR,

    I have another question. I was able to include the partial assignments and normalized efficiency. But the problem now is that when I run the code, the solution that is shown when I click on the solutions tab is 89.216. I have used a decision expression to calculate the mean absolute deviation and its value is actually 2.656.

    The expression I have used is: "minimize MeanAbsoluteDeviation" and the value for MeanAbsoluteDeviation has been calculated using other decision expressions. I don't understand why the solution in the solution tab is not 2.656 considering that uses the same decision expressions.

    I have attached the dat file and my code is shown below.

    <pre class="jive-pre"> using CP; int nTasks = ...; int nWorkers = ...; int nMachines = ...; int Demand = ...; int CycleTime = ...; int nMaxTrips = ...; {string } Tasks = ...; {string } Workers = ...; int TimeAvailableSystem = ...; int TimeAvailable[Workers]= ...; int StdOperationTimes[Tasks] = ...; tuple Skill { string Worker; string Task; float Efficiency; }; {Skill } Skills = ...; tuple PrecedenceS { string Task; {string } pre; }; {PrecedenceS } PrecedencesSet = ...; tuple PrecedencePP { string pre; string post; }; {PrecedencePP } PrecedencesPrePost = ...; float ActualOperationTimes[s in Skills] = sum(t in Tasks : t == s.Task) StdOperationTimes[t]/s.Efficiency; dvar boolean dvB[Workers][Tasks]; dvar int+ dvPartial[Workers][Tasks]; dvar int dvMachinesToTask[Tasks]; dvar interval dvTasks [t in Tasks] in 0..CycleTime; dvar interval dvWorkersToTasks [s in Skills] optional size ftoi(round(ActualOperationTimes[s])); //Theoretical work output of each task dexpr float TheoreticalProduction[t in Tasks]= sum(s in Skills : s.Task == t, w in Workers: s.Worker == w) (dvB[w][t]*dvPartial[w][t]/100)*dvMachinesToTask[t]*presenceOf(dvWorkersToTasks[s])*TimeAvailable[w]/ActualOperationTimes[s]; //Actual work output of each task dexpr float ActualProduction[t in Tasks] = minl (TheoreticalProduction[t], sum(p in PrecedencesSet : p.Task == t) min(r in p. pre) TheoreticalProduction[r]); //Total work output dexpr float TotalActualProduction = sum(t in Tasks) ActualProduction[t]; //Average work output dexpr float AvgActualProduction = TotalActualProduction/nTasks; //AbsoluteDeviation dexpr float AbsoluteDeviation[t in Tasks] = abs(ActualProduction[t] - AvgActualProduction); //MeanAbsoluteDeviation dexpr float MeanAbsoluteDeviation = (sum(t in Tasks) AbsoluteDeviation[t])/nTasks; execute { cp.param.FailLimit = 10000; } //Minimize Mean Absolute Deviation minimize MeanAbsoluteDeviation; subject to { forall(p in PrecedencesPrePost) endBeforeStart(dvTasks[p.pre], dvTasks[p.post]); forall(t in Tasks) alternative(dvTasks[t], all(s in Skills: s.Task==t) dvWorkersToTasks[s]); forall(w in Workers) noOverlap(all(s in Skills: s.Worker==w, t in Tasks : t == s.Task) dvWorkersToTasks[s]); forall(t in Tasks) dvMachinesToTask[t] >= 1; sum(t in Tasks) dvMachinesToTask[t] <= nMachines; ActualProduction[last(Tasks)] >= Demand; forall(w in Workers) sum(t in Tasks) dvPartial[w][t]==100; forall(w in Workers, t in Tasks) dvPartial[w][t] <= 100 * dvB[w][t]; forall(w in Workers, t in Tasks) dvPartial[w][t] >= 20 * dvB[w][t]; forall(w in Workers) sum(t in Tasks) dvB[w][t] <= nMaxTrips+1; }; </pre>
    Dear OptimusCP,

    I try to replicate your problem with Test6.mod and Example1.dat but unfortunately, I get the following error:

    Description Ressource Chemin d'accès Emplacement Type
    Echec du traitement. LineBalancing Inconnu Problème OPL
    Elément "nMachines" non défini. Example1.dat /LineBalancing 3:11-12 Example1.dat Problème OPL

    Could you please send the appropriate .mod and .dat file, it'll help me figuring out what is happening.

    Cheers,

    Renaud
  • GGR
    GGR
    35 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-03-22T16:48:42Z  
    Hi Optimus

    You have actually found a bug. As a workaround, I have rewritten the model:

    
    dexpr 
    
    float TheoreticalProductionpre[t in Tasks] = (sum(p in PrecedencesSet : p.Task == t) ((card(p.pre) > 0) ? (min(r in p.pre) TheoreticalProduction[r]) : 1000));
    


    The (card(p.pre) > 0) Boolean condition avoids to have an empty array of expression in the min operator. the 1000 constant is correct for the data in example1 and depends upon them.

    The optimal solution is 0 (10^-15) found in about 1 sec (on my 3 years old machine).

    Hope that helps
  • SystemAdmin
    SystemAdmin
    378 Posts

    Re: Line Balancing Problem - error in objective function

    ‏2013-03-25T20:11:19Z  
    • GGR
    • ‏2013-03-22T16:48:42Z
    Hi Optimus

    You have actually found a bug. As a workaround, I have rewritten the model:

    <pre class="jive-pre"> dexpr float TheoreticalProductionpre[t in Tasks] = (sum(p in PrecedencesSet : p.Task == t) ((card(p.pre) > 0) ? (min(r in p.pre) TheoreticalProduction[r]) : 1000)); </pre>

    The (card(p.pre) > 0) Boolean condition avoids to have an empty array of expression in the min operator. the 1000 constant is correct for the data in example1 and depends upon them.

    The optimal solution is 0 (10^-15) found in about 1 sec (on my 3 years old machine).

    Hope that helps
    @GGR,
    Thank you so much. That worked perfectly.

    @Renaud,
    It was Example1.dat and the code that was in the post. Thank you for looking into it.