Results 1 to 2 of 2

Math Help - Job Scheduling Problem

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    2

    Job Scheduling Problem

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by prasanthnath View Post
    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
    Consider stochasic search, simulated annealing or tabu search

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Production Scheduling Problem
    Posted in the Business Math Forum
    Replies: 2
    Last Post: October 25th 2012, 12:32 AM
  2. Scheduling
    Posted in the Math Puzzles Forum
    Replies: 4
    Last Post: November 12th 2009, 11:50 AM

Search Tags


/mathhelpforum @mathhelpforum