Makespan

In operations research, the makespan of a project is the distance in time that elapses from the start of work to the end. This type of multi-mode resource constrained project scheduling problem (MRCPSP) seeks to create the shortest logical project schedule, by efficiently using project resources, adding the lowest number of additional resources as possible to achieve the minimum makespan.[1] The term commonly appears in the context of scheduling. There is a complex project that is composed of several sub-tasks. We would like to assign tasks to workers, such that the project finishes in the shortest possible time.

As an example, suppose the "project" is to feed the goats. There are three goats to feed, one child can only feed one goat at a time, and there are two children that can feed them: Shmuel feeds each goat in 10 minutes and Shifra feeds each goat in 12 minutes. Several schedules are possible:

  1. If we let Shmuel feed all goats, then the makespan is 30 (3×10 for Shmuel, 0 for Shifra);
  2. If we let Shifra feed one goat and Shmuel two goats, then the makespan is 20 (2×10 for Shmuel, 12 for Shifra working beside and in parallel to Shmuel);
  3. If we let Shifra feed two goats and Shmuel one goat, then the makespan is 24 (2×12 for Shifra, 10 for Samuel working beside and in parallel to Shifra);
  4. If we let Shifra feed all goats, then the makespan is 36 (3×12 for Shifra, 0 for Shmuel).

So in this case, the second schedule attains the shortest makespan, which is 20.

Types of makespan minimization problems
  • Job shop scheduling – there are n jobs and m identical stations. Each job should be executed on a single machine. This is usually regarded as an online problem.
  • Open-shop scheduling – there are n jobs and m different stations. Each job should spend some time at each station, in a free order.
  • Flow shop scheduling – there are n jobs and m different stations. Each job should spend some time at each station, in a pre-determined order.
gollark: ... of what, our conversations with you or just anything about coronavirus?
gollark: ... okay, then...
gollark: "If you didnt do anything wrong, then you shouldnt be worried" only works if you cast "not being happy with things" as "wrong", as well as "being associated with people who did "wrong" things", and expect that people will just never care about politics.
gollark: I agree that that can sometimes be a problem, but it also means people can actually suggest improvements or dislike things without fearing for their lives.
gollark: People might disagree with how you run things and that's really not a good reason to imprison/whatever them.

References
  1. 1

[1]A solution procedure for preemptive multi-mode project scheduling problem with mode changeability to resumption, Afshar-Nadjafi, B, in Applied Computing and Informatics (2014)


  1. 1
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.