Implementing Scheduling Algorithms with Java

views:

107

answers:

+3 Q:

Implementing Scheduling Algorithms with Java

has anyone of you ever dealt with job scheduling problems with Java? I have to work on a resource-constrained project scheduling problem and want to ask for some practical tips. Are there any good libs available for implementing algorithms? What are efficient data structures I should use?

edit:

It seems like i have not explained it right. I want to solve the resource-constrained project scheduling problem (RCPSP) which is known to be NP-complete with different heuristics. The problem is defined as follows:

A project consists of a set A = {1, ..., n} of activities, which must be performed on a set R = {1, ..., m} of resources. An activity j ∈ A requires rjk ≥ 0 units of resource k ∈ R throughout its non-preemptible processing time pj ≥ 0. Each resource k ∈ R has a limited capacity Rk > 0. There exists precedence relations between the activities, such that one activity j ∈ A can not be started before all its immediate predecessors have completed. The objective is to find a precedence and resource-capacity feasible schedule which minimizes the overall makespan.

+2 A:

OpenSymphony Quartz Scheduller is the right tool for the task.

From Quartz's web page:

"What is Quartz?

Quartz is a full-featured, open source job scheduling service that can be integrated with, or used along side virtually any Java EE or Java SE application - from the smallest stand-alone application to the largest e-commerce system. Quartz can be used to create simple or complex schedules for executing tens, hundreds, or even tens-of-thousands of jobs; jobs whose tasks are defined as standard Java components that may executed virtually anything you may program them to do. The Quartz Scheduler includes many enterprise-class features, such as JTA transactions and clustering.

Quartz is freely usable, licensed under the Apache 2.0 license.

Please read our overview for more quick information."

Boris Pavlović 2010-10-08 07:42:47

That does not work for me. I added a comment to my first post to define the problem more clearly. but thx anyway.

martin 2010-10-08 08:05:38

+1 A:

JDK 1.6 already have very good one. look at java.util.concurrent.ScheduledThreadPoolExecutor

Dewfy 2010-10-08 07:44:57

Sorry obviously I stated the problem not clear enough. I added a comment to my first post to make it clearer. Thx anyway.

martin 2010-10-08 08:08:40

AMPL is a modeling language that you can use for this, it can be compiled into a mixed integer linear program and solved with a number of solvers. I would suggest the GNU MathProg modeling language, it is a subset of the AMPL language and you can use it with the GLPK solver. This is a very common problem and you will probably be able to find a example very close to what you want to do.

edit: actually glpk comes with it's own modeling language which is just a subset of AMPL, which would likely make things easier.

anonymous_21321 2010-10-15 08:32:51

Thx for the tip, but this problem is NP-hard. So the instances I have to deal with are not solvable in practical time with this methods.

martin 2010-10-19 13:14:15

I'm well aware of the computational complexity of the problem, I'm a PhD student doing research directly in this field. If anything this approach is not exactly desirable because it is too sophisticated not, as you hypothesize, too simple. If you look at any operations research in this field you will see modeling as a MILP is by far the preferred approach.

anonymous_21321 2010-10-19 19:16:14

Reference please.So if I understand you right, you are saying that I just have to transform my problem into a MILP and put it into a solver? Then why do I find on scholar.google.com a lot of papers dealing with metaheuristics like GAs and tabu search? (especially from 2008 on)

martin 2010-10-20 04:17:40

GAs and tabu are only locally optimal but tend to perform better for impossible problems, there is a lot of recent work here because people generally don't research what already works well. These algorithms are used when the problem is so large there is no hope of solving it optimally. Your original question asked for practical tips, so mine would be don't get into the world of evolutionary computation until you are sure your problem is intractable (can't be solved optimally). You can code up your problem in a day with the GLPK language, and it will probably solve it in a matter of seconds.

anonymous_21321 2010-10-20 05:37:24

Ok, now I understand :) But the thing is I also have very large instances and so I have to deal with GAs. Furthermore I will write my master thesis about that and so I will also have to tackle some PSPLIB instances for benchmarking. But thx anyway for the tip for the smaller instances.

martin 2010-10-21 07:03:01

ansaurus

tags:

views:

answers:

Implementing Scheduling Algorithms with Java

related questions