# Minimize makespan with jobs that require multiple machines

 1 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 Dunning 917●1●4●18 accept rate: 33% fbahr ♦ 4.6k●7●16

 2 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. answered 04 Dec '13, 03:56 jmonette 141●3 accept rate: 50% Project scheduling (albeit without precedence) does seem to the right literature. Thanks! (04 Dec '13, 11:45) Iain Dunning
 3 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. answered 04 Dec '13, 01:08 Ehsan ♦ 4.8k●3●11●22 accept rate: 16% 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
 0 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). answered 06 Dec '13, 08:50 Geoffrey De ... ♦ 3.6k●3●27●64 accept rate: 6%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: