One machine problem

In machine utilization planning, single -machine problems are special models with a single machine and n different orders to be produced . Although the models are relatively simple compared to job shop , open shop , or flow shop problems, some are NP-hard problems. Many, however, can be solved in polynomial time, i.e. comparatively quickly. The solution of the models depends on the desired objective. Examples are the minimization of the cycle time, the processing time or the delays. The usual notation for machine occupancy problems is [1 | | ] Problems. (For details on the notation, see Classification of Machine Occupancy Models.) Most problems can also be viewed as scheduling problems in IT: The machine then corresponds to a processor and the jobs correspond to the processes. Similarly, a machine occupancy problem with parallel machines can be interpreted as a model with several processors.

Minimization of the maximum schedule deviation

The problem [1 | | T _max ] can be optimally solved with the priority rule of the Earliest Due Date rule (EDD rule). At [1 | prec | T _max ] there is a graph with a sequence of the operations to be followed. It can be solved using Lawler's algorithm.

The problems [1 | a _j | T _max ] and [1 | a _j | V _max ] are NP-hard. If the processing of the orders can be interrupted ([1 | pmnt, a _j | T _max ] and [1 | pmnt, a _j | V _max ]), a modified (so-called dynamic) EDD rule can be solved. The orders are then planned with the smallest completion date at the time of planning (if they are already available). This can lead to the processing of an order being interrupted if another order can be scheduled that has a shorter completion date.

Minimizing the cycle time

For the problem [1 | | Z] represents an optimal solution for every assignment without idle times. If there is a priority graph for the orders ([1 | prec | Z]), then the orders must be planned in the corresponding order. If the orders are available at different times, it is [1 | a _j | Z]. The optimal solution results from sorting according to descending availability dates and planning accordingly. With [1 | n _y | Z] the orders have to be sorted and planned according to monotonically decreasing follow-up times.

An NP-hard problem is [1 | a _j , n _j | Z]. It can arise in three-stage production if the middle stage with only one machine is a bottleneck. The availability dates then correspond to the completion times of the first stage and the follow-up times to the processing times of the third stage. It also plays a role in relaxing more complex job shop problems. It is solved with the Carlier branch and bound procedure. The upper limit is determined with Schrage's algorithm (a heuristic), the lower with a modification thereof.

If there are sequence-dependent set - up times , the problem [1 | | Z] with the set-up times from order j to order k as a round trip problem. The orders correspond to the cities to be visited and the set-up times correspond to the distances between them. ${\displaystyle \tau _{jk}}$ ${\displaystyle \tau _{jk}}$

Minimizing the lead time

The general model [1 | | D] can be calculated with the effort O (n log n) using the Smith rule: You sort the orders according to increasing processing time and schedule them in this order. If the individual orders are multiplied by weights , the optimal sequence results from sorting according to increasing processing time per weight . ${\displaystyle \omega _{j}}$ ${\displaystyle {\frac {t_{j}}{\omega _{j}}}}$

[1 | pmnt, a _j | D] can be solved with the dynamic Shortest Remaining Processing Time rule.

Minimizing the number of delays

[1 | | V _# ] can be solved using Hodgson's algorithm.

See also

• Operations Research
• Lot size
• Assembly line voting
• Resources
• Machine tool
• Production Planning and Control
• Work preparation
• Production engineering

Individual evidence

1. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p. 307.
2. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, pp. 308f.
3. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p. 310.
4. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p. 313f.
5. ^ J. Carlier: The one-machine sequencing problem . European Journal of Operations Research 11, 1982, pp. 164-176.
6. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p. 314
7. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p. 326f.
8. ^ WE Smith: Various optimizers for single-stage production . Naval Research Logistics Quarterly 3, pp. 59-66.
9. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p.
10. ↑ Domschke, Scholl, Voss: Production planning: process organizational aspects . 2nd edition, Springer, 1997, p. 327