Flow shop

from Wikipedia, the free encyclopedia

In machine utilization planning , a flow shop is understood to be a class of problems in which n orders to be produced , which consist of m operations, are to be produced on exactly m machines . In contrast to job shop problems, the order of the machines on which the orders have to be processed is identical for each order. It is therefore a matter of modeling production systems with flow production . In a job shop , on the other hand, production systems are modeled with workshop production . In the case of normal flow shop problems, each order after each machine can be stored for as long as desired and thus generally also be overtaken by subsequent orders. In this case, the order sequence on the machines is different. In permutation flow shops , the order sequence is identical on every machine - orders cannot be overtaken here. Optimal permutation plans are basically easier to find. If you can show for a specific flow shop problem that there is always a permutation plan under the optimal machine assignments, you can limit yourself to this. Some problems are NP-hard problems, but others can still be solved in polynomial time. This applies in particular to more specific problems such as [PF2 | | ], ie permutation flow shops with exactly 2 machines (details on the notation under classification of machine occupancy models ). Other types of machine usage problems are job shop and open shop problems, machine usage problems with parallel machines, or machine usage problems with one machine .

Problems with two machines

Flow shop problems with two machines have been investigated since the late 1950s. They are among the simpler problems, although most of them are nonetheless NP-hard problems. Johnson examined the general case [F2 | | Z], which can be solved with the Johnson algorithm named after him with a computational effort of O (n log n). The algorithm first considers all jobs that have a shorter processing time on the first machine than on the second. These are scheduled one after the other in increasing processing time. Then the remaining orders are sorted and scheduled on the second machine according to the decreasing processing time. At [F3 | | Z] the Johnson algorithm can be used if the middle machine is not a bottleneck. This is the case if the smallest processing time on the first or last machine is greater than the largest on the second machine. You add up the processing times of the first two machines and those of the last two machines and you get a two-machine problem, which, solved with the Johnson algorithm, also provides the optimal assignment for the three-machine problem. A modification of the problem allows the orders to be processed on both machines at the same time. This is the case, for example, with loss splitting, in which the orders consist of lots that are passed on to the subsequent machine after partial completion. This problem can also be solved with the Johnson algorithm.

At [F2 | | Z], sequence-dependent set - up times are taken into account for setting up order j on order k on machine i. In this case, the cycle time also includes the set-up time. This problem and the analogous permutation problem are NP-hard. They can be as generalized traveling salesman problem ( Traveling Salesman Problem viewing / TSP). In the event that there is only one machine and all processing times t j = 0, the result is exactly the standard TSP, which is already NP-difficult. Permutation plans are generally not optimal, but they can serve as an upper bound if the problem is solved with a branch-and-bound algorithm. The lower limit is to consider only one machine at a time and solve the corresponding TSP. For this purpose, an additional order with zero processing time will be introduced. The distances of the TSP correspond to the sum of set-up and processing time. The optimal assignment for the isolated consideration of the first machine represents a lower limit for Z, since after all jobs have been processed on the first machine, at least one job has to be processed on the second. Accordingly, before the first job is processed on the second machine, at least one job must be completed on the first machine, which means that this cycle time cannot be optimal for the overall problem either.

[F2 | no wait | Z] represents a special case of the TSP, which can be solved in polynomial time due to the special structure. If the first machine is already occupied with order i, the following order k may only be completed on the first machine when order i is completed on the second machine, since otherwise the following order would have to wait. For the entries in the distance matrix , c ij : = max {t j2 , t k1 } applies .

The problem [F2 | a j | Z] is also NP-hard. A heuristic combines the Johnson algorithm and the dynamic earliest due date rule , in which the next order is scheduled, which has the earliest completion time.

[F2 | a j , n j | Z] is also NP-hard. It is solved by means of branch-and-bound processes, in which corresponding problems with a machine are used to generate the barriers.

With the NP-hard problem [F2 | | D] to minimize the lead time there are always some optimal solutions with permutation plans, so that one can concentrate on them. The solution is based on concepts for solving [PF | | Z].

General flow shops

Even the problem with three machines is NP-hard. Heuristics for normal plans are mostly based on heuristics to solve job shop problems. For [PF | | Z], however, special heuristics have been developed. They try to generalize the Johnson algorithm by scheduling jobs that have relatively low processing times on the first machines as early as possible and those with relatively high processing times on the later machines rather late. You can also try to divide the machines into two groups and add up the respective processing times to come up with two-machine problems. Better results are obtained by trying all m-1 groupings of the machines. Another possibility is to first sort the orders according to increasing sums of processing times and then to schedule them one after the other in an initially empty list. The orders are planned in each case at the position at which the current cycle time increases as little as possible due to the planning of the further order. Improvement procedures start from a permutation plan and try to improve the solution by exchanging or moving orders. The Ingall and Schrage method , which works with the branch-and-bound method, provides an exact permutation solution .

See also

Individual evidence

  1. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, pp. 285, 361 f.
  2. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, pp. 362-365.
  3. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, pp. 365-368.
  4. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p. 368 f.
  5. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p. 369.
  6. ↑ a b Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p. 370.
  7. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, pp. 375-378.