# Collaborative Process Planning on Route Market Platform

Keisuke Beppu, Hajime Mizuyama, Tomomi Nonaka

► To cite this version:

Keisuke Beppu, Hajime Mizuyama, Tomomi Nonaka. Collaborative Process Planning on Route Market Platform. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2017, Hamburg, Germany. pp.49-56, 10.1007/978-3-319-66926-7_6. hal-01707278

HAL Id: hal-01707278

https://inria.hal.science/hal-01707278v1

Submitted on 12 Feb 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Collaborative Process Planning on Route Market Platform

Keisuke Beppu, Hajime Mizuyama, and Tomomi Nonaka

Management Technology Course, Aoyama Gakuin University,
5-10-1 Fuchinobe, Chuo-Ku, Sagamihara, Kanagawa 252-5258, Japan
kei00562005@gmail.com, {mizuyama,nonaka}@ise.aoyama.ac.jp

**Abstract.** In order for a group of manufacturing SMEs to become competitive as a team, each of them should have its own strength and the strength must be united into an appealing process plan suitable for the specification of every manufacturing order. Since the detailed knowledge on the capability of each SME is owned only by the SME itself and often difficult to be disclosed to public, it is a big challenge how to properly incorporate the strength into the process plan without a single planner who knows the details of the capabilities of all SMEs. This paper calls this task as collaborative process planning, and proposes how to refine and utilize the platform of *Route Market*, which was originally developed by the authors for geographical route recommendation service, for the task.

**Keywords:** collaborative design, collective intelligence, networked SMEs, process planning, prediction markets

## 1 Introduction

There are usually several possible processing routes for manufacturing a specific part, and which to choose among them is an important decision for a manufacturer, since it affects the production costs, lead-time, and quality of the part. The task of making this decision is called process planning. Most process planning problems are mathematically captured as a problem of selecting a suitable path in a network of candidate process elements. For example, D'Souza (2006) discusses how to obtain such a network for 2.5D pocket machining process. If only a single objective function needs to be considered for each path and the function is additive in terms of the arcs, the problem becomes a well-known shortest path problem and can be solved through a suitable algorithm such as Dijkstra's algorithm. Otherwise, the problem becomes a more cumbersome combinatorial optimization problem, and it is often handled through a meta-heuristic approach. For example, Awadh et al. (1995) and Ahmed et al. (2010) applied genetic algorithms to such a process planning problem. Whereas, Li et al. (2008) employed genetic programming, and Wang et al. (2015) utilized ant colony optimization, respectively.
Thus, if the topology of the network connecting possible process elements and the attributes of each element relevant to the objective function(s) are known to a planner, what remains to be done by the planner is to solve the resultant optimization problem. However, when a group of manufacturing SMEs try to respond to various manufacturing orders competitively as a team, a different challenge emerges. To attain this goal, the strength of each SME should be united into an appealing process plan suitable for the specification of each manufacturing order. However, since the detailed knowledge on the capability of each SME is owned only by the SME itself and often difficult to be disclosed to public, this should be accomplished without a single planner who knows the details of the capabilities of all SMEs. This paper calls this challenging task as collaborative process planning, and proposes an approach to the problem utilizing *Route Market* as the platform.

*Route Market* is a geographical route recommendation service proposed by the authors (Beppu et al. 2016). This service collects information on the topology of the road network and relevant conditions of any part of the network from crowds in an incentive-compatible way using the mechanism of prediction markets, and provides several suitable routes to the one raised a query about the route. What this service carries out is to choose suitable paths in an network utilizing the collective knowledge of the crowds. When replacing the road network with the network of process elements and crowds with SMEs, it becomes apparent that this task is isomorphic to collaborative process planning. In the remainder, collaborative process planning problem is formally described first, and then how *Route Market* can be modified and used as a solution platform for the problem is discussed.

## 2 Collaborative Process Planning Problem

We consider a situation where a group of manufacturing SMEs try to win or received a manufacturing order of a part, and need to design a suitable process plan for it collaboratively as a team. The manufacturing order can be captured as a transformation of a given raw material into a specified finished part. The transformation can be made through applying several process elements to the material one by one, such as milling, drilling, polishing, etc., and there are many optional sequences of process elements, i.e. process plans, for the part. The SMEs have different capabilities in processing the part. For example, one may be good at drilling a long narrow hole into a stainless steel block in a high speed. These capabilities should be united appropriately into the plan. However, the details of the capability of each SME is private information of the SME.

When the SMEs' capabilities are known, all applicable process elements and executable process plans by them can be represented by a directed graph.

$$G = (V, A) \qquad (1)$$

This is a network like **Fig.1**, for example. In this network, a node $v \in V$ indicates the shape of a work (in progress), and each arc $a \in A$ indicates a process element.
<figure><img src="image_2.png" /><figcaption>Fig. 1. Example: Process Element Network</figcaption></figure>

Especially, the start node $v_S$ represents the raw material and the end node $v_E$ corresponds to the finished part. Any path from $v_S$ to $v_E$ is a processing route and is denoted by $p$, and the set of all feasible processing routes is represented by $\Omega$. A processing route $p \in \Omega$ is an ordered set of process elements $a$ (process elements included in the processing route $p$).

The entity placed the manufacturing order expects that the part can be manufactured in a low production costs, a short processing lead-time, and a high quality (in terms of the tolerance, surface roughness, dimensional error, shape error, etc.). If the costs for carrying out the process element $a$ is denoted by $c(a)$, the whole production costs of the processing route $p$ can be defined by the following equation.

$$c_P(p) = \sum_{a \in p} c(a) \qquad (2)$$

Similarly, if how long it takes to carry out the process element $a$ is denoted by $t(a)$, the whole processing lead-time of the processing route $p$ can be calculated as

$$t_P(p) = \sum_{a \in p} t(a) \qquad (3)$$

Further, we denote the quality characteristics, such as those described above, which can be evaluated after executing the process element $a$ as $q(a)$, and express the overall production quality obtained through a processing route $p$ by a set $q_P(p)$ as follows.

$$q_P(p) = \{q(a)|a \in p\} \qquad (4)$$

Then, how the orderer prefers a processing route $p$ can be evaluated by a multi-attribute utility function

$$F(c_P(p), t_P(p), q_P(p)) \qquad (5)$$
and the process planning problem can be captured as a problem of selecting a
processing route *p* that maximizes *F*(*c*<sub>*P*</sub>(*p*), *t*<sub>*P*</sub>(*p*), *q*<sub>*P*</sub>(*p*).

In the situation we consider in this paper, where a group of SMEs need
to deal with this problem collaboratively, each SME may have its own special
manufacturing capability, such as drilling a long narrow hole into a stainless
steel block in a high speed. Further, the details of such capability is basically
private information of the SME, and hence it is difficult to exhaustively capture
the possible process elements as well as to properly evaluate their cost, lead-time
and quality without collecting relevant private information from the SMEs.

This means that, if we denote the process element network constructed based
only on common knowledge by G₀, it is not sufficient to find an optimal path
p in G₀ in terms of the objective function F(cₚ(p), tₚ(p), qₚ(p)). It is also im-
portant to refine the network G₀ into G₁, G₂, G₃, ... by incorporating relevant
private information of the SMEs little by little. Thus, the collaborative process
planning problem considered in this paper can be modeled as a problem of re-
fining the process element network Gn and find an suitable path p in it in terms
of F(cₚ(p), tₚ(p), qₚ(p)) through interactions among the SMEs. In general, the
more informative the final network Gn is, the more preferable the output pro-
cessing route will be.

3 Route Market for Collaborative Process Planning

The original *Route Market* is refined so that it can be used as a platform for
collaborative process planning. The refined *Route Market* system links an or-
derer who poses a manufacturing order of a part and a group of manufacturing
SEMs who undertake the processing of the part as a team, and presents some
recommended processing routes to the orderer based on the information col-
lected from the SMEs. First, the orderer provides technical specifications of the
manufacturing order, that is, detailed descriptions of the raw material vS and
the finished part vE. Then, the SMEs can clearly understand that the process
of transforming vS into vE should be designed. The orderer is also expected to
present information on its preference, that is, how to balance the production
costs, processing lead-times, production quality, etc.

Then, a baseline process element network G₀ is constructed based on com-
mon knowledge and shown to SMEs. The SEMs are expected to (re-)evaluate
candidate process elements and processing routes in the network according to
their own technical capabilities and engineering knowledge. They are also in-
vited to provide a reason behind the evaluation. In addition, they can refine
the network by adding some new process elements to it. The system summa-
rizes the reasons and evaluations provided by the SEMs, and indicates several
highly-evaluated processing routes. At the end, those recommended routes are
shown to the orderer with the reasons supporting them collected from the SMEs.
Then, the orderer selects one that best meets its preference among the presented
processing routes.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Example: Adding an Arc</figcaption></figure>

This system uses the mechanism of prediction markets for motivating the SMEs to evaluate candidate paths and provide relevant information. Prediction markets are the market of a prediction security whose worth depends on the unknown realized value of a certain random variable of interest, and thus the market price of the security provides a dynamic forecast of the random variable reflecting the collective knowledge of the traders. This approach can be applied not only to forecasting problems but also to decision-making problems (Chen & Pennock, 2010, Plott 2000).

The prediction market used in the proposed system is designed according to the authors' earlier work (Mizuyama 2012, Mizuyama et al. 2013). The prediction market utilizes two types of prediction securities. One is a winner-take-all security for each path $p \in \Omega$, to which a fixed amount payoff will be given if and only if $p$ is chosen by the orderer and the orderer confirms that the path was satisfactory. Hereafter, this is called path security $p$. The other is a security corresponding to each arc $a \in A$, to which a fixed amount payoff will be given if and only if is included in the chosen path. Hereafter, this is called arc security $a$.

Path securities are useful for the system to compare different candidate routes. We can regard the price of $p$ as the evaluation of the corresponding processing route. However, it is not straightforward for the SMEs to directly trade them, especially when they are familiar with only a specific type of process elements. Thus, the proposed system lets the SMEs trade arc securities instead of path securities, and relate the two security types by treating each arc security $a$ as a bundle of path securities $p(a \in p)$.

## 3.1 How to Refine Network Topology

In order to refine the topology of the process element network, the SMEs are allowed to add new arcs to the network. For example, when a certain SEM
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Example: Providing Comments</figcaption></figure>

owns an advanced processing technology and the technology makes it possible to translate a work in progress corresponding to a node in the network into a shape specified by another node but the nodes are not connected with an arc, they can be connected with a new arc, as shown in **Fig. 2**. How to maintain the consistency among the securities when an arc is added is discussed in (Mizuyama 2012).

## 3.2 Comment Function

In the proposed system, the SMEs are also supposed to contribute information about the arcs. They can provide each arc with information related to the processing lead-time, production costs and quality, as shown in **Fig. 3**. The provided information on the arcs contained in each recommended path is shown to the orderer, when the market is closed.

## 3.3 Market Maker

To preserve smoothness in transactions, the prediction market in the proposed system utilizes an automated market maker. The most widely-used market maker algorithm for a prediction market is LMSR (Hanson 2003, Hanson 2007), but, if it is to be used as is, it cannot handle topological changes of the network. Thus, LMSR was extended, so that it can be used in the proposed system (Mizuyama 2012). A specific algorithm for this extended LMSR is described below.

The candidate process elements derived by common knowledge comprises the initial network $G_0$, and it is updated as $G_1, G_2, G_3, ...$ by adding arcs one by one. We denote the set of processing routes included in the process element networks as $\Omega_0, \Omega_1, \Omega_2, \Omega_3, ...$. It is noted here that deleting arcs is not necessary. If a certain arc is regarded to be useless, $F(c_P(p), t_P(p), q_P(p))$ will be decreased for all $p$ ($a \in p$). Thus, we can assume that $\Omega_0 \subseteq \Omega_1 \subseteq \Omega_2 \subseteq \Omega_3, ...$ holds.
Let's denote the current process element network by $G_i$ and the set of all new process elements which can be added to it as $O_i$. Then, by treating $O_i$ as a single unknown route, the definition of the processing route set $\Omega$ can be modified as follows.

$$ \Omega = \Omega_i \cup O_i \qquad (6) $$

Assuming that there are K SMEs and letting $q_{kp}$ be the number of path security $p$ possessed by SME $k$, the total number of path securities $p$ is given by the following equation.

$$ Q_p = \sum_{k=1}^{K} q_{kp} \qquad (7) $$

Then, the cost function for trading is defined by the following equation,

$$ C(Q) = b \cdot \log \left[ \sum_{p \in \Omega} s_p \cdot \exp\left(\frac{Q_p}{b}\right) \right] \qquad (8) $$

where $Q_{O_i}$ for unknown path $O_i$ is always 0. Then, the probability of $p$ becoming the best process route $s_p$ is equally initialized to $s_p = \frac{1}{|\Omega_0|+1}$, when there is no prior information. The value of parameter $b$ is adjusted according to the size of the prediction market.

When a SME buys and sells $\Delta q$ of path securities, the SME pays the following amount

$$ C(Q + \Delta q) - C(Q) \qquad (9) $$

The price expression of the path security $p$ is as follows.

$$ price_p = \frac{s_p \cdot \exp\left(\frac{Q_p}{b}\right)}{\sum_{p' \in \Omega} s_{p'} \cdot \exp\left(\frac{Q_{p'}}{b}\right)} \qquad (10) $$

We next consider the case when the network topology is changed from $G_i$ to $G_{i+1}$. In this case, the set of newly added routes $\Delta\Omega_i = \Omega_{i+1} - \Omega_i$ is regarded to be taken out from the unknown route set $O_i$. Therefore, the total sales number and prior probability of the processing route $p \in \Delta\Omega_i$ are set as follows.

$$ Q_p = 0 \qquad (11) $$

$$ s_p = \frac{s_{O_i}}{|\Delta\Omega_i| + 1} \qquad (12) $$

However, the arc securities corresponding to an existing arc $a$ included in the network $G_i$ are already sold and it may be the case that $Q_a \neq 0$ ($\exists a \in p$) holds at this point. This causes inconsistency. Therefore, we let the market maker keep the difference, so that $Q_p = 0$ holds.
# 4 Conclusions

This paper first formulates collaborative process planning problem which is faced by a networked manufacturing SMEs. Process planning is modeled as a problem of selecting a suitable path in a network representing the possible process elements and their sequences. However, none has the whole picture of the network, but the SMEs only know different aspects of it. Under the circumstances, the challenge is not simply solving an optimization problem, but also contains the phase of formulating what problem to solve, or what network to deal with. Next, the paper refines *Route Market*, which is originally developed for geographical route recommendation service, so that it can be used as a platform for collaborative process planning and describes how it works. Future research directions include testing it in a practical case.

# References

Ahmed, Z., Rahmani, K., and D'Souza, R.M.: Applications of Genetic Algorithms in Process Planning: Tool Sequence Selection for 2.5-Axis Pocket Machining, *Journal of Intelligent Manufacturing*, Vol.21, pp.462-470 (2010).

Awadh, B., Sepehri, N., and Hawaleshka, O.: A Computer-Aided Process Planning Model Based on Generic Algorithms, *Computers and Operations Research*, Vol.22, No.8, pp.841-856 (1995).

Beppu, K., Nonaka, T., and Mizuyama, H.: Route Market: A Prediction-Market-Based Route Recommendation Service, *The 4th AAAI Conference on Human Computation and Crowdsourcing: HCOMP 2016*, Austin, USA, Nov. (2016).

Chen, Y. and Pennock, D.M.: Designing Markets for Prediction, *AI Magazine*, Vol.31, pp.42-52 (2010).

D'Souza, R.M.: Selecting an Optimal Tool Sequence for 2.5D Pocket Machining While Considering Tool Holder Collisions, *journal of Intelligent Manufacturing*. Vol.17, pp.363-372 (2006).

Hanson, R.: Combinatorial Information Market Design, *Information Systems Frontiers*. Vol.5, pp.107-119 (2003).

Hanson, R.: Logarithmic Market Scoring Rules for Modular Combinatorial Information Aggregation, *Journal of Prediction Markets*, Vol.1, pp.3-15 (2007).

Li, X.Y., Shao, X.Y., and Gao, L.: Optimization of Flexible Process Planning by Genetic Programming, *International Journal of Advanced Manufacturing Technology*, Vol.38, pp.143-153 (2008).

Mizuyama, H.: A Prediction Market Approach for Collectively Solving an Undefinable Shortest Path Problem, *Transactions of JSAI*, Vol.27, No.6, pp.328-337 (2012) (in Japanese).

Mizuyama, H., Torigai, S., and Anse, M.: A Prediction Market Game to Route Selection under Uncertainty, *Lecture Notes in Computer Science*, Vol.8264, pp.222-229 (2013).

Plott, C.R.: Markets as Information Gathering Tools, *Southern Economic Journal*, Vol.67, pp.1-15 (2000).

Wang, J., Wu, X., and Fan, X.: A Two-Stage Ant Colony Optimization Approach Based on a Directed Graph for Process Planning, *International Journal of Advanced Manufacturing Technology*, Vol.80, pp.389-850 (2015).