Hi all..
We have a set of ‘m’ tasks (t1,t2,…. ,tm). The timings for the tasks are also specified.The task has several constraints such as
- 1.In order to assign an employee to a task, he needs to complete the required certification. (Note : Every task does not need a certification)
Now there are ‘n’ employees who has to be assigned the given ‘m’ tasks. The employee has several constraints such as
- 1.Each employee has his own preferred working timings.
- 2.For every four hours of work, he needs a 30 minutes break
Now the objective is to schedule the employees optimally in such a way that there is maximum workload* coverage.
*The workload is number of employees required to do a specific task.
We have tried out to solve this problem in various ways. Few of them are Bipartite matching, Maximum Coverage(Min – Max Theorem), Stable Marriage Problem, Hospital – Residents Problem, Pick up and Delivery Problem,Multiple Knapsack Problem.But we could not get it out. The problem is same with all of these models i.e. In these methods we are initially trying to create the time shifts and assign the suitable employees to them. The drawback here is either there is under staffing or the employees are getting assigned to shifts when they are not available in fact!
Here the problem is very simple(in terms of data). The task timings and employee timings overlap with each other in such a way that all of the employees may not find a perfect matching. In such a case we need to find the best feasible solution.
Any suggestion would be of great help to us.Thank You!
Prasanth. G
