Lineair programmeren

[Joran]

In een fabriek moeten zes taken worden afgewerkt. Er zijn twee machines beschikbaar,

en elke taak wordt op exact een machine bewerkt. De tijd die elke taak nodig heeft,

hangt af van de machine waarop de taak wordt ingepland. Alle relevante tijden worden

in de onderstaande tabel gegeven (in minuten). Plan de taken in op de machines zodat

de `makespan' (het tijdstip waarop de laatste taak is uitgevoerd) geminimaliseerd wordt.

Code: Selecteer alles

Job	  Tijd Machine 1	 Tijd Machine 2

1

   20

   24

2

9

15

3

8

 3

4

   37

45

5

   40

38

6

   65

70

Iemand enig idee hoe ik dit kan oplossen?

[jhnbk]

Aangenomen dat de opdrachten op elkaar volgen (geen twee job's tegelijk. Klopt dit?) Moet je volgende functie minimaliseren :

\(\begin{array}{l}65\,x_6+70\,\left( 1-x_6\right) +40\,x_5+38\,\left( 1-x_5\right) +37\,x_4+45\,\left( 1-x_4\right) +\\8\,x_3+3\,\left( 1-x_3\right) +9\,x_2+15\,\left( 1-x_2\right) +20\,x_1+24\,\left( 1-x_1\right) \end{array} \)

Uitgewerkt:

\(-5\,x_6+2\,x_5-8\,x_4+5\,x_3-6\,x_2-4\,x_1+195\)

Met

\(x_i \in \{0,1\}\)

[EvilBro]

Aangenomen dat de opdrachten op elkaar volgen

Lijkt mij gezien de vraag onwaarschijnlijk. Ik verwacht dat de machines parallel mogen werken.

[jhnbk]

Dan lijkt mij dit niet echt een LP probleem.

[Fred F.]

De term Lineair Programming (LP) wordt in de praktijk vaak losjes gebruikt voor een breed scale aan oplosmethoden voor optimalisaties.

Dit vraagstuk zou onder Integer Programming (IP) kunnen vallen, maar zonder de context van de leerstof is het moeilijk te weten wat voor oplosmethode de bedenker van het vraagstuk wil zien.

In ieder geval meen ik ook dat beide machines tegelijk in parallel werken.