Correct predictions are in blue. If we detect only a subset of a labelled sentence, we highlight the caught part as blue, the missing part light blue. False positives are in green and false negatives are in red.

Problem 102 (Worker Allocation) — Constraint detection

The factory is able to manufacture PQ pieces of one product . PQ denotes the production quantity of it . For producing , there is a need to employ some workers who have skills which are necessary for the production . The resource considered is worker who is represented by a numerical identifier , a set of skills , and a salary . These workers have an effort for each job . The effort represents the degree of dedication for one job . Formally , each worker is denoted with wi where i ranges from 1 to W -LRB- i denotes the numerical identifier of a worker -RRB- . The workers have a set of skills . Let SK be the set of skills , and sn denotes the n-th skill with n varying from 1 to N. SK = -LCB- s1 , s2 , s3 , s4 , s5 -RCB- . s1 : cut skill , s2 : embroidery skill , s3 : sew skill , s4 : decorating seaming , s5 : iron skill . The skills of worker wi will be denoted with skills $ wi \ subset SK$ , and each worker has a salary . The hourly salary of worker wi denotes with salary wi . It is supposed that a garment factory receive an order which needs to manufacture a lot of embroidery clothes . This factory plans to assign five workers to finish the clothes order . The different skills of the workers and their hourly salaries are given . w1_skill = -LCB- s1 , s3 -RCB- . w2_skill = -LCB- s2 , s4 -RCB- . w3_skill = -LCB- s2 , s3 -RCB- . w4_skill = -LCB- s5 -RCB- . w5_skill = -LCB- s1 , s4 , s5 -RCB- . w1_salary = $ 1000 . w2_salary = $ 800 . w3_salary = $ 1200 . w4_salary = $ 700 . w5_salary = $ 1500 . For example , in order to make these clothes , the workers must have five kinds of skills : cut skill , embroidery skill , sew skill , decorating seaming and iron skill . Also for example , worker w1 who earns $ 1000 every hour , has cut skill and sew skill . To plan to manufacture products , the production process is divided into several jobs . Job is modeled as following . A job is represented by a numerical identifier and a set of properties . These properties are described in the following . Jobs are denoted with jm where m ranges from 1 to M -LRB- m denotes a numerical identifier of jobs -RRB- . j1 : cut out clothes , j2 : sew the bosom of clothes , j3 : sew the sleeve of clothes , j4 : make hats , j5 : seam clothes , j6 : do embroidery , j7 : iron the clothes . Each job jm has a set of required skills associated with it denoted by skill mj and each job has production speed speed jm . Production speed represents how many products can be produced by one worker in an hour . The information of these jobs which include production speed of each job and the set of required skills are provided . j1_skill = -LCB- s1 -RCB- . j2_skill = -LCB- s3 , s4 -RCB- . j3_skill = -LCB- s3 , s4 -RCB- . j4_skill = -LCB- s1 , s3 -RCB- . j5_skill = -LCB- s3 -RCB- . j6_skill = -LCB- s2 , s4 -RCB- . j7_skill = -LCB- s5 -RCB- . j1_speed = 20 . j2_speed = 25 . j3_speed = 30 . j4_speed = 20 . j5_speed = 35 . j6_speed = 15 . j7_speed = 25 . For example job j1 needs cutting out the clothes in order to be used later by the workers , so this job needs to be assigned to workers with cut skill . And the cut speed is 20 pieces per hour per person . To assign jobs , we need to know the precedence relation of jobs firstly . The jobs must be performed according to a Job Precedence Graph -LRB- JPG -RRB- . A JPG indicates which jobs must be completed before a new job begins . The JPG is an acyclic directed graph $ G -LRB- V , A -RRB- $ with a vertex set $ V = -LCB- j1 , ... , jM -RCB- $ and an arc set A , where $ -LRB- jn , jm -RRB- \ in A$ if job jn must be completed , with no other intervening jobs , before job jm can start . Let us continue the garment factory example . The production sequence of these jobs is given in a figure . According to this graph , the production sequence can be shown , such as after job j1 cutting out clothes is completed , job j2 sewing the bosom of clothes , job j3 sewing the sleeve of clothes , and job j4 making hats can be started . Now the element of a solution to the worker allocation problem is described . A solution can be represented with a matrix of size $ W \ times M$ where $ x _ -LCB- im -RCB- \ gt 0 $ . The element $ x _ -LCB- im -RCB- $ is the effort of worker wi for job jm . The effort required to complete a job , measured in person-hours , must be known before workers can be assigned to the job . Then the work can be scheduled . If worker wi performs job jm with a 0.5 effort , he spends half of his working day on this job . If a worker does not perform a job , he will have an effort of 0 for that job . If the worker has an effort of 1.0 for one job , he spends one working day on this job . The effort of a worker for job is used to compute the duration of each job . And the starting and finishing time of each job can be calculated , i.e. , the time schedule of the jobs -LRB- Gantt diagram -RRB- can be made . A solution is expressed as a matrix whose element $ x _ -LCB- im -RCB- $ -LRB- denotes the effort of worker to job -RRB- has the value between 0 and 1 , i.e. , $ x _ -LCB- im -RCB- \ in -LSB- 0,1 -RSB- $ . The assignment of personnel to job is constrained to areas that are essential to the prototype . The percent of a worker 's labor that can be committed to any given job is constrained to a discrete set of values . The commitment quota is constrained to the set $ -LCB- 0 , 0.2 , 0.4 , 0.6 , 0.8 , 1 -RCB- $ for each worker effort that can be assigned to any single job . The objective is to minimize the human cost , the production duration and production overwork . In order to evaluate quality of a worker allocation solution , how to calculate production duration , human cost and overwork should be thought firstly . To get the production duration , denoted by $ p ^ -LCB- duration -RCB- $ , the duration of each job should be calculated firstly , denoted by $ jm ^ -LCB- duration -RCB- $ . It can be calculated as $ j_m -LCB- duration -RCB- = \ frac -LCB- PQ -RCB- -LCB- \ sum _ -LCB- i = 1 -RCB- ^ w x _ -LCB- im -RCB- \ times j_m ^ -LCB- speed -RCB- -RCB- $ . According to the duration of each job , the starting time and the finish time of each job are calculated . The production can be scheduled as in a figure . The production duration which is the maximum finish time of the production also can be calculated . The human cost denoted by $ w ^ -LCB- cost -RCB- $ is the sum of fees paid to the workers for their efforts on production . These costs are computed by multiplying the salary of the employee by the time spent on the production . The time spent on the project is the sum of the efforts multiplied by the duration of each job . The human cost can be computed as $ w ^ -LCB- cost -RCB- = \ sum _ -LCB- i = 1 -RCB- ^ W \ sum _ -LCB- m = 1 -RCB- ^ M wi ^ -LCB- salary -RCB- \ times x _ -LCB- im -RCB- \ times jm ^ -LCB- duration -RCB- $ . Finally , in order to compute the overwork $ p ^ -LCB- overwork -RCB- $ , there is need to compute the working time -LRB- denoted with $ wi ^ -LCB- work -RCB- $ -RRB- of each worker previously . For each worker wi , maximum working time as $ wi ^ -LCB- max ed -RCB- $ is defined . If his working time is larger than the maximum working time , his overwork -LRB- denoted with $ wi ^ -LCB- overwork -RCB- $ -RRB- is calculated by the working time subtract his maximum working time . If his working time is smaller than the maximum working time , his overwork is 0 . And the production overwork is calculated as -LRB- denoted with $ p ^ -LCB- overwork -RCB- $ -RRB- the sum of overwork of all workers . $ wi ^ -LCB- work -RCB- = \ sum _ -LCB- m = 1 -RCB- ^ M x _ -LCB- im -RCB- \ times jm ^ -LCB- duration -RCB- $ . $ wi ^ -LCB- overwork -RCB- = \ max -LRB- wi ^ -LCB- work -RCB- - wi ^ -LCB- max ed -RCB- , 0 -RRB- $ . $ p ^ -LCB- overwork -RCB- = \ sum _ -LCB- i = 1 -RCB- ^ W wi ^ -LCB- overwork -RCB- $ . In order to find feasible solutions , it is checked whether all jobs can be completed . If no worker is assigned to a job , the job could n't be completed . If the skills of assigned workers for a job ca n't satisfy skill requirements , the workers ca n't finish this job . So there are the constrains that each job must be performed by at least one worker . Moreover the set of required skills of a job must be included in the union of the skills of the workers performing the job . It must be checked firstly that all jobs will be performed by somebody , i.e. , no job is left undone , that is : $ \ sum _ -LCB- i = 1 -RCB- ^ w x _ -LCB- im -RCB- > 0 \ forall m \ in \ -LCB- 1 , 2 , \ ldots , M \ -RCB- $ . The second constraint of a feasible solution is that workers performing one job must have the skills required by that job : $ j_m ^ -LCB- skill -RCB- \ subset \ union _ -LCB- \ -LCB- i s.t. x _ -LCB- im -RCB- > 0 \ -RCB- -RCB- wm ^ -LCB- skill -RCB- \ forall m \ in \ -LCB- 1 , 2 , \ ldots , M \ -RCB- $ . The objective is to minimize production duration , human cost , and production overwork : $ f = v _ -LCB- duration -RCB- \ times p ^ -LCB- duration -RCB- + v _ -LCB- cost -RCB- \ times w ^ -LCB- cost -RCB- + v _ -LCB- overwork -RCB- \ times p ^ -LCB- overwork -RCB- $ . The term is the weighted sum of the production duration , human cost and production overwork . In this term , $ v _ -LCB- duration -RCB- $ , $ v _ -LCB- cost -RCB- $ and $ v _ -LCB- overwork -RCB- $ are values weighting the importance of the three objectives . The minimum value of the term f can be found .

Problem 102 (Worker Allocation) — Detection of the decisions and objects to be modeled

The factory is able to manufacture PQ pieces of one product . PQ denotes the production quantity of it . For producing , there is a need to employ some workers who have skills which are necessary for the production . The resource considered is worker who is represented by a numerical identifier , a set of skills , and a salary . These workers have an effort for each job . The effort represents the degree of dedication for one job . Formally , each worker is denoted with wi where i ranges from 1 to W -LRB- i denotes the numerical identifier of a worker -RRB- . The workers have a set of skills . Let SK be the set of skills , and sn denotes the n-th skill with n varying from 1 to N. SK = -LCB- s1 , s2 , s3 , s4 , s5 -RCB- . s1 : cut skill , s2 : embroidery skill , s3 : sew skill , s4 : decorating seaming , s5 : iron skill . The skills of worker wi will be denoted with skills $ wi \ subset SK$ , and each worker has a salary . The hourly salary of worker wi denotes with salary wi . It is supposed that a garment factory receive an order which needs to manufacture a lot of embroidery clothes . This factory plans to assign five workers to finish the clothes order . The different skills of the workers and their hourly salaries are given . w1_skill = -LCB- s1 , s3 -RCB- . w2_skill = -LCB- s2 , s4 -RCB- . w3_skill = -LCB- s2 , s3 -RCB- . w4_skill = -LCB- s5 -RCB- . w5_skill = -LCB- s1 , s4 , s5 -RCB- . w1_salary = $ 1000 . w2_salary = $ 800 . w3_salary = $ 1200 . w4_salary = $ 700 . w5_salary = $ 1500 . For example , in order to make these clothes , the workers must have five kinds of skills : cut skill , embroidery skill , sew skill , decorating seaming and iron skill . Also for example , worker w1 who earns $ 1000 every hour , has cut skill and sew skill . To plan to manufacture products , the production process is divided into several jobs . Job is modeled as following . A job is represented by a numerical identifier and a set of properties . These properties are described in the following . Jobs are denoted with jm where m ranges from 1 to M -LRB- m denotes a numerical identifier of jobs -RRB- . j1 : cut out clothes , j2 : sew the bosom of clothes , j3 : sew the sleeve of clothes , j4 : make hats , j5 : seam clothes , j6 : do embroidery , j7 : iron the clothes . Each job jm has a set of required skills associated with it denoted by skill mj and each job has production speed speed jm . Production speed represents how many products can be produced by one worker in an hour . The information of these jobs which include production speed of each job and the set of required skills are provided . j1_skill = -LCB- s1 -RCB- . j2_skill = -LCB- s3 , s4 -RCB- . j3_skill = -LCB- s3 , s4 -RCB- . j4_skill = -LCB- s1 , s3 -RCB- . j5_skill = -LCB- s3 -RCB- . j6_skill = -LCB- s2 , s4 -RCB- . j7_skill = -LCB- s5 -RCB- . j1_speed = 20 . j2_speed = 25 . j3_speed = 30 . j4_speed = 20 . j5_speed = 35 . j6_speed = 15 . j7_speed = 25 . For example job j1 needs cutting out the clothes in order to be used later by the workers , so this job needs to be assigned to workers with cut skill . And the cut speed is 20 pieces per hour per person . To assign jobs , we need to know the precedence relation of jobs firstly . The jobs must be performed according to a Job Precedence Graph -LRB- JPG -RRB- . A JPG indicates which jobs must be completed before a new job begins . The JPG is an acyclic directed graph $ G -LRB- V , A -RRB- $ with a vertex set $ V = -LCB- j1 , ... , jM -RCB- $ and an arc set A , where $ -LRB- jn , jm -RRB- \ in A$ if job jn must be completed , with no other intervening jobs , before job jm can start . Let us continue the garment factory example . The production sequence of these jobs is given in a figure . According to this graph , the production sequence can be shown , such as after job j1 cutting out clothes is completed , job j2 sewing the bosom of clothes , job j3 sewing the sleeve of clothes , and job j4 making hats can be started . Now the element of a solution to the worker allocation problem is described . A solution can be represented with a matrix of size $ W \ times M$ where $ x _ -LCB- im -RCB- \ gt 0 $ . The element $ x _ -LCB- im -RCB- $ is the effort of worker wi for job jm . The effort required to complete a job , measured in person-hours , must be known before workers can be assigned to the job . Then the work can be scheduled . If worker wi performs job jm with a 0.5 effort , he spends half of his working day on this job . If a worker does not perform a job , he will have an effort of 0 for that job . If the worker has an effort of 1.0 for one job , he spends one working day on this job . The effort of a worker for job is used to compute the duration of each job . And the starting and finishing time of each job can be calculated , i.e. , the time schedule of the jobs -LRB- Gantt diagram -RRB- can be made . A solution is expressed as a matrix whose element $ x _ -LCB- im -RCB- $ -LRB- denotes the effort of worker to job -RRB- has the value between 0 and 1 , i.e. , $ x _ -LCB- im -RCB- \ in -LSB- 0,1 -RSB- $ . The assignment of personnel to job is constrained to areas that are essential to the prototype . The percent of a worker 's labor that can be committed to any given job is constrained to a discrete set of values . The commitment quota is constrained to the set $ -LCB- 0 , 0.2 , 0.4 , 0.6 , 0.8 , 1 -RCB- $ for each worker effort that can be assigned to any single job . The objective is to minimize the human cost , the production duration and production overwork . In order to evaluate quality of a worker allocation solution , how to calculate production duration , human cost and overwork should be thought firstly . To get the production duration , denoted by $ p ^ -LCB- duration -RCB- $ , the duration of each job should be calculated firstly , denoted by $ jm ^ -LCB- duration -RCB- $ . It can be calculated as $ j_m -LCB- duration -RCB- = \ frac -LCB- PQ -RCB- -LCB- \ sum _ -LCB- i = 1 -RCB- ^ w x _ -LCB- im -RCB- \ times j_m ^ -LCB- speed -RCB- -RCB- $ . According to the duration of each job , the starting time and the finish time of each job are calculated . The production can be scheduled as in a figure . The production duration which is the maximum finish time of the production also can be calculated . The human cost denoted by $ w ^ -LCB- cost -RCB- $ is the sum of fees paid to the workers for their efforts on production . These costs are computed by multiplying the salary of the employee by the time spent on the production . The time spent on the project is the sum of the efforts multiplied by the duration of each job . The human cost can be computed as $ w ^ -LCB- cost -RCB- = \ sum _ -LCB- i = 1 -RCB- ^ W \ sum _ -LCB- m = 1 -RCB- ^ M wi ^ -LCB- salary -RCB- \ times x _ -LCB- im -RCB- \ times jm ^ -LCB- duration -RCB- $ . Finally , in order to compute the overwork $ p ^ -LCB- overwork -RCB- $ , there is need to compute the working time -LRB- denoted with $ wi ^ -LCB- work -RCB- $ -RRB- of each worker previously . For each worker wi , maximum working time as $ wi ^ -LCB- max ed -RCB- $ is defined . If his working time is larger than the maximum working time , his overwork -LRB- denoted with $ wi ^ -LCB- overwork -RCB- $ -RRB- is calculated by the working time subtract his maximum working time . If his working time is smaller than the maximum working time , his overwork is 0 . And the production overwork is calculated as -LRB- denoted with $ p ^ -LCB- overwork -RCB- $ -RRB- the sum of overwork of all workers . $ wi ^ -LCB- work -RCB- = \ sum _ -LCB- m = 1 -RCB- ^ M x _ -LCB- im -RCB- \ times jm ^ -LCB- duration -RCB- $ . $ wi ^ -LCB- overwork -RCB- = \ max -LRB- wi ^ -LCB- work -RCB- - wi ^ -LCB- max ed -RCB- , 0 -RRB- $ . $ p ^ -LCB- overwork -RCB- = \ sum _ -LCB- i = 1 -RCB- ^ W wi ^ -LCB- overwork -RCB- $ . In order to find feasible solutions , it is checked whether all jobs can be completed . If no worker is assigned to a job , the job could n't be completed . If the skills of assigned workers for a job ca n't satisfy skill requirements , the workers ca n't finish this job . So there are the constrains that each job must be performed by at least one worker . Moreover the set of required skills of a job must be included in the union of the skills of the workers performing the job . It must be checked firstly that all jobs will be performed by somebody , i.e. , no job is left undone , that is : $ \ sum _ -LCB- i = 1 -RCB- ^ w x _ -LCB- im -RCB- > 0 \ forall m \ in \ -LCB- 1 , 2 , \ ldots , M \ -RCB- $ . The second constraint of a feasible solution is that workers performing one job must have the skills required by that job : $ j_m ^ -LCB- skill -RCB- \ subset \ union _ -LCB- \ -LCB- i s.t. x _ -LCB- im -RCB- > 0 \ -RCB- -RCB- wm ^ -LCB- skill -RCB- \ forall m \ in \ -LCB- 1 , 2 , \ ldots , M \ -RCB- $ . The objective is to minimize production duration , human cost , and production overwork : $ f = v _ -LCB- duration -RCB- \ times p ^ -LCB- duration -RCB- + v _ -LCB- cost -RCB- \ times w ^ -LCB- cost -RCB- + v _ -LCB- overwork -RCB- \ times p ^ -LCB- overwork -RCB- $ . The term is the weighted sum of the production duration , human cost and production overwork . In this term , $ v _ -LCB- duration -RCB- $ , $ v _ -LCB- cost -RCB- $ and $ v _ -LCB- overwork -RCB- $ are values weighting the importance of the three objectives . The minimum value of the term f can be found .

Back to list