I have a set of jobs \(J_1\) to \(J_n\) and a set of machines types \(M_1\) to \(M_m\). There may be 1,2, or maybe even 3 of each type of machine - typically 1 though. Each job takes a fixed time \(T_i\), and requires a some amount of each type of machine. I'm trying to minimize makespan (total time to complete the jobs).

Example:

  • Job 1 requires Machines A and B for 2 hours
  • Job 2 requires Machine A for 1 hour
  • Job 3 requires Machine B for 1 hour
  • Min makespan = 3 hours

The question is: are there nice known algorithm for this in the literature? I'm struggling to find it due to a lack of familiarity with the language of the area, and would rather not reinvent the presumably dynamically programmed wheel.

asked 04 Dec '13, 00:29

Iain%20Dunning's gravatar image

Iain Dunning
9171418
accept rate: 33%

edited 04 Dec '13, 04:15

fbahr's gravatar image

fbahr ♦
4.6k716


I would add to Ehsan answer that the "Resource Constrained Project Scheduling Problem" (RCPSP) might also be relevant. You can represent your "machine types" by "cumulative resources" and the amount of available resource is the number of machines of this type.

Actually your problem is even simpler as you do not seem to have precedences constraints between jobs (but I think this is still NP-hard).

In a constraint programming setting (with support for scheduling like, e.g. OPL, Comet, Gecode, or OscaR to name a few), you can express your problem as (using a made up syntax similar to Comet or OPL):

Activity job1 = new Activity(2); // job1 is processed for two hours
Activity job2 = new Activity(1);
Activity job3 = new Activity(1);

Resource machineA = new Resource(1); //there is one machine of type A
Resource machineB = new Resource(1);

job1.require(machineA,1); //job1 must be executed using 1 machine of type A
job1.require(machineB,1);
job2.require(machineA,1);
job3.require(machineB,1);

minimize max(job1.end,job2.end,job3.end); //minimize the maximum of the completion times (i.e. the makespan, assuming the earliest starting time of all tasks is 0).

A good introductory book on constraint-based scheduling is "Constraint-based scheduling: applying constraint programming to scheduling problems" by Philippe Baptiste, Claude Le Pape, and Wim Nuijten.

link

answered 04 Dec '13, 03:56

jmonette's gravatar image

jmonette
1413
accept rate: 50%

edited 04 Dec '13, 03:59

Project scheduling (albeit without precedence) does seem to the right literature. Thanks!

(04 Dec '13, 11:45) Iain Dunning

This could be either a flow shop scheduling problem, in which all the jobs have the same processing order, or a jobshop scheduling problem, where there is no universally common processing order for all the jobs. Also, if the order of processing tasks is not important for each job, this would be a open scheduling problem. These are usually NP-hard problems. The exceptions usually happen when there are a limited number of machines (at most, three machines) or specific patterns on processing times.

If you could us give more detail on which problem you're trying to solve, perhaps we could provide you with a specific reference on what you want to do.

link

answered 04 Dec '13, 01:08

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 04 Dec '13, 02:23

This is really all the detail there is unfortunately, there is no more structure to the problem than I stated.

The number of machines is likely to be small (<10), and I think I'll round the times so hopefully I'll be able to scale them nicely.

I agree that it seems to be an NP-hard problem.

(04 Dec '13, 11:44) Iain Dunning

You might also want to look at the MISTA 2013 challenge (and any papers about that). It's basically a more complex version of your problem. Just configure only 1 executionMode per job and remove all precedence constraints and you almost have your problem.

Here's my video that explains it too and shows my implementation (do note that the video does not show multiple resources used by 1 job, but mista2013 does support it).

link

answered 06 Dec '13, 08:50

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k32764
accept rate: 6%

edited 06 Dec '13, 10:36

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×6

Asked: 04 Dec '13, 00:29

Seen: 2,011 times

Last updated: 06 Dec '13, 10:36

OR-Exchange! Your site for questions, answers, and announcements about operations research.