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.

Task

Please devise an algorithm which assigns tasks to users, in a way that

Score = AverageLateness + 1000/Profit

is minimized. AverageLateness is calculated over all tasks, a task finished on time or earlier has zero lateness. Profit is simply the total value of tasks minus cost of doing them according to the generated plan. The score is chosen in such a way that AverageLateness occupies 3 higher digits after comma (is rounded to 3 digits), while 1000/Profit typically occupies digits 4-6 after comma.

Ten example configurations can be found in demo.zip. Note: you must be registered in this challenge in order to access all challenge files.

Format of the configuration file:
N Users
M Skills
[X lines of: user id, skill id of this user, quantity user can do daily, this user daily skill usage cost]
1st_userID 1st_skillID daily_quantity daily_cost
1st_userID 2nd_skillID daily_quantity daily_cost
...
1st_userID last_skillID daily_quantity daily_cost
2nd_userID 1st_skillID daily_quantity daily_cost
...
2nd_userID last_skillID daily_quantity daily_cost
...
N-th_userID 1st_skillID daily_quantity daily_cost
...
N-th_userID last_skillID daily_quantity daily_cost
[empty line]
K Tasks
[Y lines of: task_id, skill id required, quantity of task to do, value of task, time in days to do the task]
1st_taskID skillID quantity value timeleft
2nd_taskID skillID quantity value timeleft
...
n-th_taskID skillID quantity value timeleft

Daily quantities of users and task are integer numbers. Daily work costs and values of tasks are 0.1 precision floats. Timelefts are 0.01 precision floats.

Your algorithm must be implemented in Java. As a solution, compiled code should be submitted in a form of a JAR archive, with a public class of any name (you must type the class name on Submit form) containing:

static String run(String conf)

method that implements the algorithm: takes configuration as a String and outputs the plan as a String. View the Baseline algorithm class for an example. You are free to use parts of the Baseline code, such as parsing, in your own algorithm.

The output plan should comprise a number of lines, each one terminated with "\n". Every line should specify what task will be done next by a given user and in what quantity. Lines should be formatted as:

userID taskID quantityToDo

where IDs correspond to IDs in configuration file and quantityToDo must be an integer >= 1.

This information is enough to reconstruct an exact schedule, including timings, for all the users and calculate the score. For your own in-house experiments and scoring of plans, it may be helpful to use the source code of evaluation procedure.

Preliminary evaluation is executed over 5 different configurations, and the score is averaged over all of them. Final evaluation will employ 15 different configurations, to guarantee high precision of results.

There is a time limit for evaluation. Your algorithm should spend no more than 5 minutes per configuration. Memory limit is 1GB. Tests will be executed on a single-core 2.8 GHz CPU with Debian operating system, under Sun Java Runtime Environment.
Copyright © 2008-2013 by TunedIT
Design by luksite