Challenges / Algorithm for Optimal Job Scheduling and Task Allocation under Constraints

Status Closed
Type Industrial
Start 2011-04-29 17:00:00 CET
End 2011-06-13 23:59:59 CET
Prize 1,500$

Registration is required.

Overview

 
 
The challenge is over now. Click here to view the Summary.
 
 
Job scheduling is a common problem in many different applications. However, there is no algorithm that can solve this problem exactly, finding optimal solution in a reasonable time, for any large configuration of jobs and workers. In this challenge, we ask you to devise possibly most efficient intelligent heuristic for the problem of jobs allocation under constraints. Two best solutions will be awarded with $1,000 and $500 of prizes, and the winning algorithms will be disclosed publicly as open source on TunedIT pages. The challenge is organized by a US-based online marketing company, WL Marketing.

There are tasks:
T1, Q1, V1, D1
T2, Q2, V2, D2 etc.

where Tx is the task type, Qx is the quantity, Vx is the value of the task, and Dx is the amount of time remaining.

There are users with skills:
U1
T1, Q1, C1
T2, Q2, C2 etc.

U2
T1, Q1, C1
T2, Q2, C2 etc.

where Tx is the task the user can do, Qx is the quantity the user can do per day, and Cx is the cost of the user doing Tx for one day. A user can only perform so much per day, so if he performs say 1/2 day of T1, he can then only perform 1/2 day of T2.

The goal is to implement an algorithm to assign tasks Tx to users Ux efficiently such that the total profit (Vx-Cx) is maximized without items being late. View the Task page for details.

Some notes about the problem and datasets:
  • Users can do any % of a task if it doesn't precisely fit within a day.
  • Users normally have just 4 or so different skills.
  • Total number of skills can range between 100-1000+.
  • Number of users is 1-10 thousand.
  • Number of tasks is up to a million.
Prizes

Two best solutions will be awarded with prizes funded by WL Marketing:
  • USD 1,000 for the 1st winner
  • USD 500 for the runner-up
Awarded teams will release their algorithms as open source, on GNU General Public License. The algorithms will be posted in TunedIT Repository and on these pages.

How to start?

View current preliminary standings, register as a participant, download example algorithm & evaluation, download example tasks configurations, then devise your own algorithm and submit for evaluation. You can improve and resubmit your algorithm as many times as you wish. If you have any questions, ask them on the forum.

Good luck!

Note

WL Marketing has job openings currently. You are welcome to apply!

Copyright © 2008-2013 by TunedIT
Design by luksite