Topic
• 10 replies
• Latest Post - ‏2013-03-25T20:11:19Z by 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 nStations = ...;
int nWorkers = ...;

int CycleTime = ...;

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

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

int TimeAvailableWorkers = ...;

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

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

dvar interval dvWorkersToTasks s in Skills optional;

dexpr float TheoreticalProductiont in Taskss in Skills =

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

//Average work output
dexpr float AvgTheoreticalProduction =

//Minimize Mean Absolute Deviation

minimize sum(t in Tasks, s in Skills)

subject to
{
forall(p in Precedences)
forall(w in Workers)
};

#### Attachments

Updated on 2013-03-25T20:11:19Z at 2013-03-25T20:11:19Z by SystemAdmin
• GGR
44 Posts

#### Re: Line Balancing Problem - error in objective function

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

The problem comes from an indexation error

``````
dexpr

```

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.
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.

I tried running it again. The code runs for about 45 min and gives me a solution which contains 3 indexes:

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)

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

#### Re: Line Balancing Problem - error in objective function

‏2013-03-01T14:42:23Z

I tried running it again. The code runs for about 45 min and gives me a solution which contains 3 indexes:

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)

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 nStations = ...;
int nWorkers = ...;

int CycleTime = ...;

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

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

int TimeAvailableWorkers = ...;

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

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

dvar interval dvWorkersToTasks s in Skills optional;

sum(s in Skills : s.Task == t, w in Workers: s.Worker == w)

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

//Average work output
dexpr float AvgTheoreticalProduction =

execute
{
cp.param.FailLimit = 10000;
}

//Minimize Mean Absolute Deviation

subject to
{
forall(p in Precedences)
forall(w in Workers)

};
I have also attached the mod file.

• GGR
44 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.
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.
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.
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 nWorkers = ...;

int nMachines = ...;

int Demand = ...;

int CycleTime = ...;

int nMaxTrips = ...;
{string
{string
} Workers = ...;

int TimeAvailableSystem = ...;

int TimeAvailable[Workers]= ...;

int StdOperationTimes[Tasks] = ...; tuple Skill

float Efficiency;
};
{Skill
} Skills = ...; tuple PrecedenceS
{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

//Theoretical work output of each task dexpr

//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

//AbsoluteDeviation dexpr

float AbsoluteDeviation[t in Tasks] = abs(ActualProduction[t] - AvgActualProduction);
//MeanAbsoluteDeviation dexpr

{ cp.param.FailLimit = 10000;
}
//Minimize Mean Absolute Deviation minimize MeanAbsoluteDeviation; subject to
};```
```

• rdumeur
36 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
44 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
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.