Fichas

OST

Marie Scholten logistik Alemán 78 fichas

Fichas del conjunto (78)

1On what does the complexity of a method depend on?- Available software
- cost/benefit analysis
- complexity of planning problem
Heuristics for "np-hard" problems: Computational effort increases with dimension faster than any polynomial
2Heuristic types- Starting Heuristics, constructive heuristics: quickly generate a hopefully good initial solution
- Improvement Heuristics: Starting from a feasible initial solution find a better one
- Combination of starting & improvement
The 3 methods above typically get caught in a local optimum
- Metaheuristic: general, not problem specific, generic principles to generate and control heuristics, attempt to excape local optima
3Most common distance measures- Euklidean distance (Luftlinie)
- Manhattan distance
- Maximum distance
4Euklidean DistanceBeeline distance between points x and y in space
5Manhattan Distance- Distance in a rectangular road network.
- Often also applicable in building with aisles/corridors
6Maximum Distance- Movement of cranes, plotters, drilling machines, ...
- Several motors can operate at the same time
7Definitions GraphSeveral points (nodes) are connected with each other by lines.
Complete Graph: each pair of nodes is connected by a direct edge.
- An edge of a graph is called directed or arrow if the direction is given
- If all edges in a graph are directed, the graph is called directed graph
- If all edges in a graph are not directed, the graph is called non-directed graph
- A mixed graph contains directed and undirected edges
8Definition Chain- Chain between nodes i and j: sequences of edges connecting these 2 (undirected)
- Path: directed chain
9Definition CycleCycle: Chain connecting a node with itself, where no edge is traversed more than once
10Definition Treeconnected Graph, that contains no cycles. A Graph is connected, if for each pair of nodes there exists a chain connecting these two.
A graph always has (n-1) edges, every node is connected and no cycles.
11Planning problems on graphs- minimal spanning tree (MST)
- Shortest Path (From Source to Sink)
- Maximal flow (each edge has a capacity. which paths should be used and how many trips/vehicles should be planned along each path in order to maximize the # of tourists that can visit point T)
- Traveling salesman problem (Each node must be visited at the end of each day).
12Kruskal Algorithm1. Choose the shortest edge in the graph and connect the adjacent (benachbarte) edges.
2. Choose the node that is closest to an already connected node.
3. Repeat until all nodes are connected (n-1 iterations)
13Shortest PathVarious algorithms available.
Two main classes:
- Tree algorithms: Find the shortest path from one node (source) to one other node, or to all other nodes. In doing so, a tree is constructed. (Bellman, Dijkstra)
- Algorithms finding the shortest distance between all pairs of nodes. Whole distance matrix is constructed simultaneously -> tripel algorithm
14Bellman Algorithm(Simplest tree algo.):
1. Start with source as the only marked node
2. From each marked node find the non-marked node with the shortest distance
3. Among all these candidates choose the non-marked node with the shortest total distance to origin
15Dijstra AlgorithmA more efficient way to find the shortest path (same steps, just avoiding duplicate sorting efforts).
d(i,j)=length of directed edge from i to j
if no directed edge: d(i,j)=♾️
Initialize: n=0
All nodes i get a preliminary value of D[i]=d(0,i). Only the source has a final value zero. The immediate predecessor if i is denoted by V[i]. Initially V[i]=O
Iteration: n
1. Choose the node (not finally marked) with the smallest preliminary value D[i] and mark this as the final value (shortest distance to origin). This is the n-th next node to the origin.
2. Its shortest distance to O is now D[i] and the immediate predecessor is V[i].
3. Find all nodes j, that can be reached from i using a direst edge i-j. If D[i] + dij < D[j] then first going to i (at cost D[i]) and then using the edge i-j is better than the previously best path with cost D[j]
Then, set D[j] = D[i] + dij and V[j] = i.
4. If sink (or all other nodes) is/are finally marked -> stop.
16Median Problem (Single Location)Given: Set of customers & set of potential locations
b(j): demand of customer j
d(i,j): distance
𝞭(i): sum[d(i,j)*b(j)]
1. Calculate cost matrix [c(i,j)=d(i,j)*b(j)]
Per row (locations) compute the comulated costs.
2. Pick and build the location with the min total delivery cost if all customers are served form this location (min cost sum).
17Center Problem (Single Location)c(i,j) is interpreted as disutility of customer j visiting facility i.
Goal: Minimize the maximum disutility! (not total costs)
Steps same as median problem but disutility instead of costs are added up.
18Warehouse Location Problem (multiple locations) Goal & HeuristicsMinimize total cost = transportation cost + fixed cost
Construction heuristics (determine a feasible starting solution) e.g. ADD and DROP
Improvement heuristics (improve a starting solution using exchanges).
19ADD heuristicInitialization:
1. Determine location with minimal total costs [sum(c(k)+fixedCosts(k)] and "open" this location.
2. For all not opened locations determine reduction in transportation costs ω(i,j)=max{c(k,j)-c(i,j),0} and compute the row sum ω(k) (=total reduction of delivery costs, by additional location i)
Iteration: In each iteration exactly one "don't know yet" location is finally built (the one that maximizes ω(k)-fixedCosts(k).
Furthermore, all locations can be finally closed where ω(k)<=f(k)
Per iteration (re)calculate ω(i,j)=max{ω(i,j)-ω(k,j),0} for all "don't know yet"
Stop once "don't know yet" set is empty
20DROP heuristicThe Drop Algo. works the other way round compared to ADD (it starts with all potential locations to be open).
Initialisation: I(1,vl)={all locations}; I(0)=I(1)={}
Iteration:
- In each iteration one location out of I(1,vl) is finally closed. It is the one where the closing causes the highest cost redution.
- If closing a location from I(1,vl) would increase total cost, it can be finally built.
For efficient implementation 4 additional lines are added to transp cost matrix C:
- For each column j = 1, …, n, rows m+1 and m+2 of C hold the smallest (ch1j) and second smallest (ch2j) element of this column. Only rows which are not finally deleted are considered.
- In rows m+3 and m+4 we put the row numbers, where the smallest (h1) and second smallest (h2) cost elements occur. If location h1 (from I1vl) is closed, the transportation cost increase for customer j by ch2j - ch1j
21Improvement for WLPIn each iteration you can do:
- Replace a built location (from I(1)) by a forbidden location (from I(0)). Choose first improvement of best improvement
- Using rules of DROP-Algorithm delete 1 or more locations, so that cost decrease most (or increase least) and then apply ADD as long as cost savings are possible.
- Using rules of ADD-Algorithm add 1 or more locations, so that cost decrease most (or increase least) and then apply DROP as long as cost savings are possible.
22Branch & Bound for WLBB&B is an exact solution procedure for (mixed) integer programming problems
Basic Ideas:
- Starting from a root node construct a tree by branching
- Constructing the whole tree would mean complete enumeration
- Cutting away whole branches (bounding) is essential
Example: 3 warehouses
XXX-> possible values: 0/1/?
01?-> 1 is closed, 2 opened, 3 don't know
Root node: ???
In each branching step, one chooses one node still having some ?
this node is split; put 1 in one child and 0 in the other
Complete enumeration of the 2^n solutions gives complete tree
Per Node a LB(=Lb(fix)+LB(tr)) is computed
LB(fix): Treats ? as 0 (closed) and commulates the fixed costs
LB(tr) treats ? as 1 (open) and comulated cheapest var costs per customer of opened warehouses
A single UB is computed (best known solution from e.g. ADD or DROP heuristic). If LB>UB -> delete node
23P-Median (Location)# of facilities is fixed; Typically fixed costs are not needed (but can be considered if not uniform)
Exact solution: MIP with MIP solver or B&B
Heuristic: Add, Drop,...
24Transportation Problem- In order to evaluate the transportation cost for a capacitated version of the WLP, the solution of the „transportation problem“ is needed.
- A set of customers has to be serviced
- A set of locations (suppliers) is available, and all their supply must be used
Total demand = total supply
- Transportation cost per unit from each location to each customer is given
- Find the optimal delivery plan where the total transportation cost is minimized
Solution: Simplex-Method -> not very efficient if the whole matrix is used
25Capacitated WLPDifference to Uncapacitated WLP:
- The potential locations have a capacity
- The transportation cost from i to j are now per unit cost
- The demand quantities of the customers are explicitly given
- x(i,j) is now the quantity that is sent from location i to customer j
Because of capacity constraints 2 things can happen, that were not possible for uncapacitated WLPs:
1. Some customers receive quantities from more than 1 supplier
2. Some customers are not (only) serviced from the closest supplier
26ADD & DROP for the capacitated WLP- Each time a configuration (location opened/closed) is evaluated, a transportation problem has to be solved.
- In order to overcome imbalances between supply & demand: Dummy must be introduced.
27Facility LayoutAn efficient layout facilitates and reduces costs of material flow, people, and information between areas.
4 concepts will be introduced here:
- Fixed-position layout:
Large, bulky workpieces (ships, bridges, buildings, …)
- Job shop production (Process/Function-oriented production):
High variety, low volume
- Cellular manufacturing systems:
Individual products
- Flow shop production (Object-oriented production):
Low variety, high volume
28Fixed Position LayoutWorkpiece too large to be moved-> processes are brought to product.
Processes are arranged in the right sequence around the workpiece.
29Job Shop LayoutHigh variety - low volume (rapid changes in mix or volume)
- Each processing department/cell containing a collection of machines processing similar operations
- Each product (group) undergoes a different sequence of operations
- different products have different material flows and are moved from one department to another in the appropriate sequence
- high degree of interdepartmental flow
Elimination of negative effect-> optimized machine allocation; Assignment problems: Linear or Quadratic assignment problem (LAP & QAP)
30Cellular Manufacturing System
31Cellular Manufacturing System (Traditional Shapes for cells)
32Flow Shop Layout
33What does the selection of the layout depend on?- Characteristic of workpiece
- variety of production
- volume of production
34Advantages & Disadvantages of fixed-position layoutAdvantages:
- Material movement is reduced.
- Promotes job enlargement by allowing individuals or teams to perform the “whole job”.
- Highly flexible; can accommodate changes in product design, product mix, and production volume.
- Independence of production centres allows scheduling to achieve minimum total production time.
Disadvantages:
- Increased movement of personnel and equipment.
- Equipment duplication may occur.
- Higher skill requirements for personnel.
- General supervision required.
- Cumbersome (umständlich) and costly positioning of material and machinery.
- Low equipment utilization.
35Advantages & Disadvantages of Job Shop Production LayoutAdvantages:
- Better utilization of machines can result -> fewer machines are required.
- A high degree of flexibility exists relative to equipment or manpower allocation for specific tasks (break down,…)
- Comparatively low investment in machines
- The diversity of tasks offers a more interesting and satisfying occupation for the operator.
- Specialized supervision is possible.
Disadvantages:
- Longer flow lines are needed -> material handling is more expensive.
- Production planning and control systems are more involved than for other layouts.
- Usually, total production time is longer than for other layouts.
- Due to the fact that jobs have to queue before being processed in a machine job comparatively large amounts of in-process inventory occur.
- Comparatively high degree of (machine) idle time
- Space and capital are tied up by work in process.
- Because of the diversity of the jobs in specialized departments, higher grades of skill are required.
36Linear Assignment Problem- Given: m machines, n potential locations, c(i,j) cost of running machine i on location j.
- It is required to use all locations by assigning eactly one machine to each location (if m!=n -> dummy).
- Total cost of the assignements are to be minimized!
1. Perform cost reduction (subtract the smallest value of a column from all values in this column; then do the same for all rows)
If solution found: Reduced values = Total assignment costs
37Kuhn's Algorithm1. Cost reduction -> Generation of 0 elements (row minus min value)
2. Try to determine the optimal assignment. If this is not possible, draw the minimum number of lines necessary to cover all zeros in the matrix
3. Adapt the cost factors in the matrix and return to step 2.
Step 2 (detail): Frame a zero with as less as possible other 0 in corresponding col or row. Cross the other 0 values (in corr. col&row). Go on to next zero with as less as ...
Stop when all 0's are crossed or framed. If we are able o make a zero cost assigment for all machines -> optimal solution; Otherwise: mark all rows with no FRAMED 0; Mark all cols with at least 1 crossed 0 in a marked row; Mark all rows having a framed 0 in a marked col. Repeat until nothing left to mark. If # of lines = # of rows/cols, an optimal assignement is already possible.
Step 3 (detail). The smallest not-covered element is the new reduction value (a) - subtract (a) from all not-covered elements in the matrix and add (a) to all elements covered by two lines; Elements covered by 1 line remain unchanged
38LAP with MaximizationSome assignment problems entail, e.g., maximizing profit instead of minimizing cost. To convert a maximization problem to an equivalent minimization problem, we subtract every number in the original matrix from the largest single number in that matrix.
Then we can e.g. apply the kuhn algorithm
39Flow shop layoutUniform material flow:
- Linear arrangement (in most cases)
- Useful if (and only if) only one kind of product or a limited amount of different kinds of products is manufactured (low variety - high volume)
According to time-dependencies we distinguish between:
- Flow shop production without fixed time restriction for each workstation (Reihenfertigunng)
- Flow shop production with fixed time restriction for each workstation (Assembly line balancing)
40Flow shop production without fixed time restriction for each workstation- Intermediate inventories are needed
- Material flow should be similar for all products
- Some workstations may be skipped, but going back to a previous department is not possible
- Processing times may differ between products
41Flow shop production with fixed time restrictionFixed time restriction for each workstation:
- Balancing problems
- Cycle time: UB for the workload of each workstation
- Idle time: if the workload of a station is smaller than the cycle time.
Production lines, assembly lines:
- Automated system (simultaneous shifting)
- Production rate = Reciprocal of cycle time
- Workers proceed within their station parallel with their workpiece until it reaches the end of the station; afterwards they return to the beginning of the station
=>Further possibilities:
- Line stops during processing time
- Intermittent transport: workpieces are transported between the stations
42Simple assembly line balancing problem assumptions- Each operation is assigned to exactly 1 station & each station contains 1 or more operations
- 1 homogenous product is produced by performing n operations
- Precendence graph exists
- same cycle time for all stations
- fixed starting rate ("Anstoßrate")
- all stations are equally equipped (workers & utilities)
- no parallel stations
- workpieces are attached to the line
43SALBP (Main) Objectives1: cycle time is given, minimization of # of stations (m)
2. # of stations is given, minimization of cycle time (c) or maximization of production rate
3. Maximization of efficiency ("Bandwirkungsgrad")
44Alternative objectives for SALBP 3Max of BG is equivalent to:
- Min of total processing time (D=m*c)
- Min of sum of idle times (L=m*c- sum[t(j)])
- Min of ratio of idle time (LA=L/mc=1-BG)
- Min of total waiting time (W=D-sum[t(j)]=L)
45Priority Rule MethodsA non-assigned operation j can be assigned to station k if:
- All precedessors are already assigned to a station and
- the remaining idle time in station k is >= the processing time of operation j
Start: Determine list (L(s)) by applying a priority rule
Iteration: k:=k+1; Assign one operation after another as long as capacity is left
Result: L(p) contains a valid sorted list of operations with m=k stations
46Priority rules1: Random choice of operations
2: Choose operations due to decreasing (or increasing) processing time t(j)
3: Choose operations due to decreasing (or increasing) number of direct followers |N(j)|
4. Choose operations due to increasing depths of operations in G (number of arcs in the longest way from a source of the graph to j)
5. Choose operations due to decreasing positional weight (t(j)+sum[t(alleNachfolger)]
6. increasing upper bound for the minimum number of stations needed for j and all it´s predecessors {t(j)+sum[t(alleVorgänger)]}/c
7. increasing upper bound for the latest possible station of j:
m-{t(j)+sum[t(alleNachfolger)]}/c
47More flow shop heuristicsStochastic elements for rules 2-7:
- Random selection of the next operation
- Selection probabilities: proportional to the priority value
- Random chosen priority rule
Enumerative heuristics:
- Determination of the set of all feasible assignments for the first station
- Choose the assignment leading to the minimum idle time
- Proceed the same way with the next station, and so on (greedy)
Exchange methods:
- exchange of operations between stations -> Improvement in terms of subordinate objective of equally utilized stations
48Worst-case analysis of flow shop heuristicsTotal workload of 2 neighbored stations has to exceed the cycle time
49Iterative approach for determination of minimal cycle time (Flow shop)1. Calculate the theoretical minimal cycle time : max{sum[t(j)] / #of stations ; t(max)}
2. Find an optimal solution for c with minimum m(c) by applying methods presented for alternative 1
3. If m(c) is larger than the given # of stations: increase c by delta (integer value) and repeat step 2
Repeat until feasible solution with cycle time <= c and number of stations <=m is found
If delta>1, an interval reduction can be applied: if for c a solution with # of stations <=m has been found and for c-delta not, one can try to find a solution for c-delta/2 and so on...
50Classification (Oberkategorien) of complex line balancing problems1. Number of products
2. Assignment restrictions
3. Parallel stations
4. Equipment of stations
5. Station boundaries
6. Starting rate
7. Connection between items and transportation systems
8. Different technologies
9. Objectives
51Number of products (Classification of complex line balancing problems)Single product models:
- 1 homogenuous product on 1 assembly line
- Mass production, serial production
Multi-product models: Combined manufacturing of several prodcuts on 1 (or more) lines:
- MIXED MODEL: Mixed-model-assembly: Products are variations (models) of a basic product -> they are processed in mixed sequences and no setup is required
- MULTI-MODEL: Lot-wise multiple-model-production:
Set-up between production of different products is necessary
52Assignment restrictions (Classification of complex line balancing problems)Restricted utilities:
- Stations have to be equipped with an adequate quantity of utilities
- given environmental conditions
Positions: Given positions of items within a station -> some operation may not be performed then
Operations: Minimum or maximum distances between 2 operations (concerning time or space)
Qualifications: Combination of operations with similar complexity
53Parallel stations (Classification of complex line balancing problems)Models without parallel stations: Heterogenuous stations with different operations -> serial line
Models with parallel stations:
- At least 2 stations performing the same operation
- Alternating processing of 2 subsequent operations in parallel stations
Hybridization: Parallelization of operations: Assignment of an operation to 2 different stations of a serial line
54Equipment of stations (Classification of complex line balancing problems)1 worker per station
Multiple workers per station:
- Different workloads between stations are possible
- short term capacity adaption by using "jumpers"
Fully automated stations:
- Workers are used for inspection of processes
- Workers are usually assigned to several stations
55Station boundaries (Classification of complex line balancing problems)Closed stations:
- Expansion of station is limited
- Workers are not allowed to leave the station during processing
Open stations:
- Workers may leave their station in or in reverse flow direction of the line
- Short-term capacity adaption by under- and over-usage of cycle time
56Starting rate (Classification of complex line balancing problems)Models with fixed starting rate: Subsequent items enter the line after a fixed time span
Models with variable starting rate:
- An item enters the line once the first station of the line is idle
- Distances between items on the line may vary (in case of multiple product production)
57Connection between items and transportation systems (Classification of complex line balancing problems)Unmoveable items
- Items are attached to the transportation system and may not be removed
- Maybe turning moves are possible
Moveable items:
- Removing items from the transportation system during processing is allowed (post-production & itermediate inventories)
- Flow shop production without fixed time constraints for each station
58Different technologies (Classification of complex line balancing problems)Given production technologies (Schedules are given)
Different technologies:
- Production technology is to be chosen
- Different alternative schedules are given (precendence graph) and/or
- different processing times for 1 operation
59Objectives (Classification of complex line balancing problems)Time-oriented objectives:
- Minimization of total cycle time, total idle time, ratio of idle time, total waiting time
- Maximization of capacity utilization (system`s efficieny) – most relevant for (single-product) problems
- Equally utilized stations
Further objectives:
- Minimization of number of stations in case of given cycle time
- Minimization of cycle time in case of given number of stations
- Minimization of sum of weighted cycle time and weighted number of stations
Profit-oriented approaches:
- Maximization of total marginal return
- Minimization of total costs (Machines & utility costs, labour costs, material costs, idle time costs)
60Avoiding unequally utilized stationsDelta = sum(k->m&v->p)[tau(k,v)-tau(v)]
... sum of absolut deviation in utilization
Start: Deviation delta=0
Iteration (until non assigned jobs are available):
Increase k by 1
determine all feasible assignments D(k) for the next station k
Choose S(k) with the min sum of deviation [Delta(S(k))=sum(v->p)(tau(kv)-tau(v)]
Delta=Delta+Delta(S(k))
Line balancing depens on demand value. Changes in demand -> Balancing has to be revised and further machine setups have to be considered.
Workaround: Delta'=sum(k->m&v->p)[tau'(k,v)-tau'(v)]... sum of absolute deviation in utilization per unit
Disadvantages of this objective: Large deviations for a station may lead to interruptions in production. They may be compensatied by lower deviations in other stations -> Delta(max)=Max{tau'(k,v)-tau'(v)}
61Group technology (GT)Obersation already in 1920ies: product oriented departments to manufacture standardized products in machine companies lead to reduced transportation. Parts with similar features are manufactured together with standarzied processes -> small "focused factories" are created as independent operating units within large facilities.
When to use GT?
- Pure item flow lines are possible, if volumes are very large.
- If volumes are very small, and parts are very different, a functional layout (job shop) is usually appropriate
- In the intermediate case of medium-variety, medium-volume environments, group configuration is most appropriate
62Cellular Manufacturing- Principle of GT: divide the manufacturing facility into small groups or cells of machines -> cellular manufacturing
- Each cell is didicated to a specified family of part types. Preferably all parts are completed within one cell
- Typically it consists of a small group of machines, tools and handling equipment
63Different Versions of group technologyThe idea of GT can also be used to build larger groups, such as for instance, a department, possibly composed of several automated cells or several manned machines of various types
- GT flow line (closest to flow shop)
- classical GT cell
- GT center (closest to job shop)
64GT flow lineAll parts assigned to a group follow the same machine sequence and require relatively proportional time requirements on each machine.
=> mixed-model assembly line
65classical GT cellAllows parts to move from any machine to any other machine. Flow is not unidirectional.
Since machines are located in close proximity => short and fast transfer is possible.
66GT center- Machines located as in a process (job shops)
- But each machine is dedicated to producing only certain Part families => only the tooling and control advantages of GT; increased material handling is necessary
- When large machines have already been located and cannot be moved, or
- When product mix and part families are dynamic => would require frequent relayout of GT cell
67Cellular manufacturing - Advantages- Short transportation and handling (usually within cell)
- Short setup times because often same tools and fixtures can be used (products are similar)
- High flexibility (quick reaction on changes)
- Clear arrangement, few tools/machines => easy to control
- High motivation and satisfaction of workers (identification with “their" products)
- Small lot sizes possible
- Short flow times
68How to build groups (Cellular manufacturing)Smiliar parts (similar process flow/machine usage, same material,...) are grouped
-Visual inspection
- Classification and coding based on design and production data (time consuming, no universally applicable system is available)
- Production Flow Analysis (PFA)
69Production Flow Analysis classification (Cellular Manufacturing)Part family grouping: Form part families and the group machines into cells
Machine grouping: Form machine cells based upon similarities in part routing an then allocate parts to cells
Machine-part grouping: Form part families and machine cells simultaneously
70Machine part grouping (PFA-Cellular Manufacturing)Construct matrix of machine usage by parts: sort rows (machines) and cols (parts) so that a block-diagonal shape is obtained.
There are various heuristic and exact methods have been developed. The simplest one is binary ordering, also known as "rank order clustering" or "King's algorithm"
71Binary Ordering (Machine part grouping)Interpret rows and columns as binary numbers: Sort rows and columns w.r.t decreasing binary numbers (figure). This can be done several times. Items that still are not in "Blocks" must be produced in both cells or corresponding machines have to be duplicated.
72Single-Pass Heuristic, considering capacities (Askin and Strandridge)- All parts must be processed in one cell (machines must be duplicated, if off-diagonal elements in matrix)
- All machines have capacities (normalized to be 1)
- Constraints on number of identical machines in a group
- Constraints on total number of machines in a group
Step 1: Aquire block diagonal structure (e.g. using binary sorting)
Step 2:
- Assign parts to groups (in sorting order)
- Necessary machines are also included in group
- Add parts to group until either the capacity of some machine would be exceeded or the maximum number of machines would be exceeded
NOT necessarily optimal
73Similarity Coefficients & Hierarchical Clustering Heuristic (machine part grouping clustering method)n(i): # of parts visiting machine i
n(i,j): # of parts visiting machine i and j
s(i,j)=max{n(i,j)/n(i) ; n(i,j)/n(j)}: similarity coefficient, Proportion of parts visiting machine i that also visits machine j
1. Calculate Similarity Coefficients (SC) for all combinations of machines
2. Group that combination leading to the highest SC. Stopping criteria: e.g. SC have to reach a given LB, or only machines (no clustering can be grouped,...
3. Update SC: e.g. maximum of the SC of the machines that are to be combined (this is some kind of LB, determining the new coefficients exactly could lead to higher values)
74Dendogram (Similarity Coefficient solution)Graphical illustrations of possible groupings per threshold
75Graph Partitioning (machine part grouping clustering method)Given a graph with nodes and edges, find a partitioning of the node set into a (given) number of disjoint subsets of approximately equal size, such that the total cost of edges that connect nodes of different subsets is minimized.
-> Group forming can be seen as special case of graph partitioning
NP-hard optimization problem, barious methods have been developed -> simple and well-known heuristic by kernighan and Lin
76Grouping without binary ordering (Key machine)1. The machine with the fewest part types is called the "key" machine. A subgroup is formed from all the parts that visit this key machine along with all machines required by these part types.
2. Check if (except for key machine) the machines in the subgroup fall into two or more disjoint sets with respect to the parts they service. If disjoint subsets of the subgroup exist, the subgroup is again subdivided into multiple subgroups. If any machine is included in the subgroup due to just one part type, then this machine is termed "exceptional" and removed.
Step 1 & 2 are repeated until all parts and machines are assigned to subgroups.
3. The final step involves combining subgroups into groups of the desired size. Subgroups with the greatest number of common machine types are combined.
77In AP, we consider demand as deterministic, because...considering demand in a stochastic fashion does not allow for covering effects like trends or seasonality.
78—