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]);
};
Topic
This topic has been locked.
10 replies
Latest Post
 20130325T20:11:19Z by SystemAdmin
ACCEPTED ANSWER
Pinned topic Line Balancing Problem  error in objective function
20130228T01:26:48Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Attachments
Updated on 20130325T20:11:19Z at 20130325T20:11:19Z by SystemAdmin

ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130228T17:57:48Z in response to SystemAdminHi
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.
ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130301T05:49:53Z in response to GGRThank 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?
ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130301T14:42:23Z in response to SystemAdminI 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.Attachments



ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130301T15:37:30Z in response to SystemAdminHi
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.
ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130301T21:35:46Z in response to GGRThank 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.

ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130322T00:04:53Z in response to SystemAdminThe value of the objective function that is generated by the CPLEX engine is different from the value that is calculated by a decision expression.
ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130322T00:14:22Z in response to SystemAdminHey 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; };
Attachments

ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130322T16:23:31Z in response to SystemAdminDear 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:1112 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



ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130322T16:48:42Z in response to SystemAdminHi 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
ACCEPTED ANSWER
Re: Line Balancing Problem  error in objective function
20130325T20:11:19Z in response to GGR@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.
