Machine occupancy problem with parallel machines

from Wikipedia, the free encyclopedia

Machine allocation problems with parallel machines are special models in machine allocation planning with several machines working in parallel in a single production stage and n orders to be processed . The jobs can usually only be processed by one machine at a time. A distinction is made between identical parallel (IP) machines, uniform parallel (UP) machines in which the processing times of the i-th machine differ by a factor p i from a basic processing time , and heterogeneous parallel (HP) machines in which j and each machine i the processing times t ij can be different. (t ij is the processing time of job j on machine i) So we are dealing with the problems [IP | | ], [UP | | ] or [HP | | ]. (For details on the notation, see Classification of Machine Occupancy Models .) In computer science , the models can be viewed as problems with multiple processors . The machines then correspond to the processors and the orders to the processes. Other types of machine usage problems are job shop , flow shop , open shop problems or machine usage problems with a machine . Problems with several production stages and parallel machines are special flow shop problems, so-called hybrid or flexible flow shops.

Identical machines

Minimizing the cycle time

The problem [IP | pmnt | Z] is particularly easy to solve, in which in addition to the n interruptible (pmnt) jobs, m machines are available and the cycle time Z is to be minimized, i.e. the time from the start of processing the first job to End of the last job. If there are at least as many machines as there are jobs, each job is processed immediately and the cycle time corresponds to the longest processing time t max . If fewer machines are available, the optimal cycle time is Z = t sum / m with t sum as the sum of the individual processing times. A machine occupancy results from assigning jobs to the first machine until the total processing time is exactly the same as the optimal cycle time. (Since the orders can be interrupted, this type of assignment is always possible. An interrupted order is then processed on another machine.) The procedure is then repeated until all orders have been scheduled. This process is also known as the pagination method.

The problem [IP | | Z], without interruptible jobs, belongs to the class of NP-hard problems. It can be formulated as follows:

If you ignore the last line, you get the problem [IP | pmnt | Z], the solution of which can thus serve as an estimate. One heuristic for the solution is to sort the orders according to monotonously decreasing processing times. Then you schedule the jobs in this order on the machine that is least occupied. Exact solutions are possible with dynamic programming or branch and bound algorithms.

With [IP | in-tree, t j = 1 | Z], all orders have the same processing time and there is a priority graph in the form of a tree, with only a single end product to be manufactured and several intermediate products. It can be solved with the so-called Highest Level First method, in which the order j is assigned a rank value that corresponds to the number of arrows pointing from j to n, and the orders are then scheduled according to falling rank values. If there is a priority graph in the form of a forest, i.e. several unconnected trees, you can connect the end products with an additional (fictitious) node and get a tree again. With [IP | out-tree, t j = 1 | Z] there is also a priority graph in the form of a tree, in which, however, several intermediate and end products are produced from a single starting product. It can be solved analogously if one chooses the number of arrows in the longest path from j to an end product as the rank value.

Minimizing the lead time

With [IP | | D] you want to minimize the lead time . To do this, the machine with the lowest occupancy is assigned the job that has the shortest processing time (shortest operation time rule / shortest processing time rule).

Uniform machines

Uniform machines only differ in terms of their different production speeds. The processing times t ij therefore differ for different machines i only by a factor p i .

Minimizing the cycle time

The general problem [UP | | Z] is NP-hard. It is solved by modifying the solution method of [IP | | Z]. As a heuristic, the orders are again sorted according to decreasing processing times. There are two alternatives available for deciding on which machine the jobs should then be scheduled:

  • a) The machine that would finish the job earliest at the current planning time.
  • b) The machine with the lowest occupancy time.

If one rule does not provide a clear decision, the other rule is chosen. If this does not provide a clear decision either, the machine with the smallest i is selected.

The problem [UP | t j = 1 | Z] can be solved in polynomial time by formulating it as a transport problem and using the special algorithms that are suitable for it. The orders correspond to the suppliers and every combination of order and machine corresponds to a customer. The transport costs c kij correspond to the completion times if order j is produced as the kth order on machine i.

Minimizing the lead time

[UP | | D] is similar to [IP | | Z]. One method is the Horowitz and Sahni algorithm .

Heterogeneous machines

With heterogeneous machines, there are processing times t ij that can be different for each machine and each order. The problems are almost always NP-hard.

The problem [HP | pmnt | Z] can be solved by first determining the optimal cycle time with a linear system of equations. The jobs are then distributed to the machines using the make-up method, as with [IP | pmnt | Z].

[HP | | D] can be solved with polynomial effort by formulating it as a transport problem. The orders then correspond to the providers with an offer quantity of 1 (each order must be executed exactly once). The machines appear n times as consumers.

See also

literature

  • Blazewicz, Ecker, Pesch, Schmidt, Weglarz: Handbook on Scheduling , Springer, 2007, pp. 137–199. (Chapter "Scheduling on parallel Processors")
  • Jaehn, Pesch: Sequence planning , Springer, 2014, pp. 51–71 (chapter "Models with parallel machines")
  • Brucker: Scheduling Algorithms , Springer, 2007, 5th edition, pp. 107–155 (chapter "Parallel Machines")
  • Pinedo: Scheduling , Springer, 4th edition, 2012, pp. 111–150 (chapter "Parallel Machine Models (Deterministic)), pp. 295-320 (Chapter" Parallel Machine Models (Stochastics))

Individual evidence

  1. ↑ a b c d e f g Domschke, Scholl, Voß: Production planning: process organizational aspects . 2nd edition, Springer, 1997
  2. ^ Graham, Lawler, Lenstra, Rinnooy Kan: Optimization and approximation in deterministic sequencing an scheduling: A survey . Annals of Discrete Mathematics 5, 1979, pp. 287-326.
  3. ↑ Horowitz, Shahni: Exact and approximate algorithms for scheduling nonindentical processors . Journal of the ACM 23, 1976.