Definition of the problem in the branch and bound method

## 1. Introduction

The level of a service and its cost have a trade-off relation in the supply chain, but most companies aim to achieve both quality service and low cost at the same time by means of effective supply chain management. In an effort to achieve this goal, many researches have been made to minimize the uncertainties related to the supply chain through its effective design and operation. It is noteworthy that the goal of each participant in the supply chain does not lead to the maximization of the efficiency and effectiveness of the supply chain (Lee & Billington, 1992; Towill, 1996). Therefore, the cooperative effort between the members in the supply chain is needed to respond to the customer’s demand effectively. This indicates that the integration concept from the viewpoint of the whole supply chain is necessary. Traditionally, more efforts have been made to remove the imbalance of supply and demand in the production management, generally putting emphasis on reducing a total cost (Bowersox & Closs, 1996). Also, most preceding studies have focused on the flexible organization in the vertical integration as shown in the companies having a controlling power in the supply chain.

However, this study has focused on the competitive relations between participants in the horizontal integration instead of the vertical one. In the competitive relations, a certain number of buyers and manufacturers usually make a decision only depending on the price information because of no further information sharing (Bylka, 2003). But manufacturers in the horizontal integration, although they keep a competitive relation between them, are trying to have a strategic cooperation with others by means of sharing information on their order situation.

Related to the topic, several research studies have been conducted with concepts such as supply chain collaboration, supply chain coalition, and supply chain configuration. Moyaux et al. (2004) experimented with three levels of collaboration schemes regarding demand information transmission among supply chain members to reduce the bullwhip effect. They adopted game theory with multi-agent simulation and showed that they can reach Nash equilibrium and minimum supply chain cost. Nagarajan and Sosic (2006) reviewed coalition formation models in a supply chain from the viewpoint of game theory. They suggested new ideas such as foresightedness among supply chain players and future research in applying cooperative game theory to supply chain management.

As a solution to the problems of supply chain configuration, this study has used agent negotiation. Due to dynamic changes in the internal and external environments, it is not easy to coordinate the conflicts of interests among supply chain members. What’s more, quick response to those dynamic changes is required. Coordination of activities across a network of suppliers is essential for reacting quickly to uncertain environments (Chan, H. & Chan, F., 2010). For this reason, the use of an agent system has come to the fore. An agent system uses a coordination mechanism to approach a global optimization, along with the local objective of each agent. In addition, negotiations are widely being used as a coordination mechanism (Guan, 1995).

The use of intelligent software agents along the supply chain has been investigated by a number of researchers. The benefits of adopting agent technology in supply chains have been recognized in an increasingly wide variety of applications involving inter-enterprise collaboration, extending the boundaries of strategic partnership to wherever the network technologies can reach. One way that such agents can be adaptive is to consider multiple ways to solve their sub-problems so that they can adjust their solution to produce the best possible result, subject to the restrictions on available processing, communications and information resources, etc (Lin et al., 2008). A number of recent studies have led to significant advances by placing more emphasis on complexity and dynamics of supply chains (Caridi & Cavalieri, 2004). Monteiro et al. (2007) addressed a hierarchical architecture to integrate individual planner agent, negotiator agent, and mediator agent with a decentralized control for achieving robustness and flexibility of the supply chain network. To model and simulate complex supply chains in a mass customization context, Labarthe et al. (2007) proposed a methodological framework based on an agent paradigm. Forget et al. (2008) explored a framework to design multi-agent behavior in a supply chain planning system, where agents were able to dynamically change their planning and coordination mechanism and, ultimately increase overall performance. Min and Bjornsson (2000) presented a conceptual model of agent-based supply chain automation, in which a project agent gathers actual construction progress information and sends to subcontractor agents and supplier agents, respectively, over the Internet. They evaluated an agent-based SCM model compared with traditional SCM practice through simulation.

Most work in this area has concerned with distributed planning and scheduling system that models the supply chain as a set of semi-autonomous and collaborative entities acting together to coordinate their decentralized plans.

This paper has defined this relationship as a subcontract environment. This study assumes that the manufacturing cost of each manufacturer is based on the SET model(Single Machine Earliness/Tardiness Model). Therefore, the total manufacturing costs involving earliness production cost and tardiness production cost can be changed according to which order is placed with which member. In other words, we assume that the manufacturing cost can be changed according to what orders can be placed together.

Actually, when making a decision by price information only, manufacturers become rivals to receive an order from the buyer, but in the subcontract environment, they can maximize their profits by means of a cooperative relation, while optimizing the whole cost from the viewpoint of the supply chain.

This paper runs as follows. The second chapter deals with the preceding studies on SET model, introduces the scheduling applied to this study, and defines the problem of the supply chain in this study. Chapter 3 introduces the optimal solution by means of the Branch & Bound method. Chapter 4 presents the negotiation method and its algorithm, while testing the optimal solution of the negotiation method through experiments. Chapter 5 comments on the limit of this study and future research direction.

## 2. Definition of the problems in the SET model

### 2.1. Single machine earliness & tardiness model

The scheduling problems can diversely be categorized as a single machine, parallel machine, flow shop, and job shop. With regard to the scheduling problems, this study, however, has focused on a single machine, because the SET model is widely used due to the advantage that it incurs the least tardiness production cost and earliness production cost when a due date is not met (Pinedo, 2001).

The dynamic supply chain means an environment in which a large number of orders can be carried out by numerous manufacturers, previous orders can be cancelled, and new orders can be added. Moreover, since multiple manufacturers are in a competitive relationship, it is possible for all the orders to go to one manufacturer, or no orders to go to a certain manufacturer.

Since the concept of “just-in-time” was introduced in 1980’s in Japan with regard to the studies on scheduling, the importance of irregular measure, which considers earliness and tardiness simultaneously, has been emphasized (Kim & Yano, 1994). In particular, Baker and Scudder (1990) had defined an Earliness and Tardiness model(E/T model) in the single machine according to the assumption of the objective function and restricted conditions. The basic objective function of E/T model in the single machine can be defined as follows.

E_{i} : earliness, T_{i} : tardiness

C_{i} : completion date, d_{i} : due date

E_{i} = max{0, d_{i}-C_{i}} = (d_{i}-C_{i})^{+}

T_{i} = max{0, C_{i}-d_{i}} = (C_{i}-d_{i})^{+}

α_{i}, β_{i} : a unit earliness penalty, a unit tardiness penalty

In the formula 1, the tardiness cost is caused by breaking the duty of observing a due date, and the earliness cost comes from the inventory cost. And a manufacture should bear both costs of tardiness and earliness. Therefore, an ideal scheduling demands to finish each job in its due date. In other word, the purpose of scheduling is to minimize the deviation of the due date and the job completion, that is, to minimize the total amount of tardiness cost and earliness cost (refer to formula 2), (Baker & Scudder, 1990; George, 1997; Kim & Yano, 1994; Peng, 1989).

### 2.2. Definition of problems

This problem deals with the case of a make-to-order manufacturing company. Accordingly, its production begins after accepting an order from the buyer, and the manufacturing company doesn’t keep inventory in advance in its factory. As shown in the <formula 3>, the manufacturer puts emphasis on the due date considering the CTP (Capable To Promise) function, which is composed of the manufacturing cost, tardiness cost, and earliness cost.

In particular, the problem of breaking the duty of observing the due date is considered in this section. It means the processing time of the product order cannot meet the distinct due date of the order (Kim & Yano, 1994).

Concerning the range of the supply chain, this paper has dealt with the relationship between multiple buyers and multiple manufacturers. As shown in the <figure 1>, multiple buyers make requests for the estimates of more than one from all the manufacturers in the supply chain. And the manufacturers who have received a request for an estimate are making preparations to establish an optimal scheduling. In this case, let’s suppose that there is no difference in the product’s quality of each manufacturer, but some difference in their production cost according to the CTP function. Also this study supposes that the orders from the buyers are placed at the same time or in a nearly the same time.

In the <figure 1>, the manufacturer A, B, and C have received a request of the estimate for order 1 from buyer A, and then establish a scheduling for production. Soon after that, they have also received a request of the estimate for order 2 from a new buyer B, and so they are making a rescheduling for both orders. In this case, the manufacturer A’s scheduling changes like <figure 2>. In the second scheduling, the manufacturing priority for each order is to be made based on the E/T model. At this time, the processing for the priority order (order 1) can cause an earliness cost due to early production, and the processing for the next order (order 2) can cause a tardiness cost owing to the delayed due date.

The rescheduling that has to consider all orders simultaneously causes both an earliness cost and a tardiness cost, and these additional costs will increase in proportion to the deviation between the due date and the order fulfillment date (refer to the formula 2). This production cost increase is to happen likewise to the other manufacturers.

Based on the expected orders, manufacturers are to make scheduling and rescheduling, and then offer the buyers their production cost estimated on the basis of the rescheduling. If the number of orders decreases because of competition between manufacturers, the actual manufacturing cost will be lower than the cost based on the scheduling, thus causing the difference between both of them. This difference can cause the danger of losing competitiveness. Another difficulty follows when the manufacturer has accepted an order at a lower price than its production cost because of competition with his rival. In addition to these, there are a burden on keeping the delivery time and a late response to the buyer’s demand. All these problems lead to the imbalance of supply and demand, thus making it difficult to achieve an optimization. In order to solve these problems, this paper has suggested a negotiation method that gives priority to the strategic alliance between manufacturers.

## 3. Optimal solution based on the branch & bound algorithm

The branch & bound algorithm has been introduced for an optimal solution in this section. This method is different from the branch & bound algorithm applied to the ordinary scheduling. As the supply chain environment is under the competitive situation, two cases can be considered. The first is that one manufacturer handles all the orders, and the other is that other manufacturers join in fulfilling the orders. In the latter case, it is important how to distribute the orders among those manufacturers. The branch and bound method can be explained as follows by means of a simple scenario.

As shown in the <table 1>, let’s suppose that there are three manufacturers and three orders, and that since the written estimates of manufacturer A are lowest, all the buyers has simultaneously placed their orders with the manufacturer A. In this case, the A has to make a rescheduling for three orders, and the new estimate based on this rescheduling is much higher due to the SET model than the first estimate. Because of this, the A has to reduce these production costs by means of cooperation with other manufacturers. When all the orders have been placed with the A, the possible combinations between manufacturers and orders are shown in the below <table 2>.

Manufacturer A | Manufacturer B | Manufacturer C | |||||||

O 1 | O 2 | O 3 | O 1 | O 2 | O 3 | O 1 | O 2 | O 3 | |

1^{th} Scheduling | 10 | 12 | 15 | 12 | 14 | 16 | 13 | 16 | 23 |

2^{nd} Rescheduling | 13 | 18 | 21 |

Order combination Member (Manufacturer) | {1} | {2} | {3} | {1,2} | {1,3} | {2,3} | {1,2,3} |

A | 80 | 60 | 50 | 150 | 160 | 150 | 220 |

B | 30 | 90 | 20 | 130 | 140 | 200 | |

C | 80 | 40 | 140 | 130 | 100 | 210 |

In the case of <table 2>, considering the number of members and order combinations, iterative allocation has to be conducted 21 times in total. Under the assumption that we know all the costs, each cost table by branch should be made. However, in an effort to overcome a full search, this study has introduced a newly developed heuristic Branch-and-Bound method. This has the following strategies that do not depend on a full search.

Strategy 1: the total manufacturing cost in the optimal solution is at least the same or less than that of all the orders placed with one manufacturer. In the first branch, the manufacturer that has the least cost for all the orders will be the first starting point in branching. This manufacturing cost is the first bound.

Strategy 2: The series of branches that have generated the least value will be the same as the optimal solution or near to it. Therefore, a lower branch is basically inherits the bounds of upper branches.

This strategy should be more efficient than a full search algorithm. Therefore, branching starts from ‘n’ number of simultaneous orders that have generated the first bound, and the lower branch inherits the order combination of the upper branch. At this time, the lower branch will have one less order combination than the number of order combinations of the upper branch, i.e. n-1 order combinations. This new Branch-and-Bound method is a heuristic Branch-and-Bound. Therefore, it does not guarantee optimality but stops sooner than a full search. The algorithm of the heuristic Branch-and-Bound method is as follows.

Step 0: When each manufacturer has ‘n’ number of orders placed, calculate each sum of the cost of orders assigned to each manufacturer. The order set assigned to a manufacturer i that has the least sum of cost becomes the starting order-manufacturer combination Ts. Name this starting set of orders as Oi for further consideration. Name the set of manufacturers that are not the ‘i’ manufacturer as L.

Step 1: Remove each order from Oi and assign it to a manufacturer in L. Select the least cost manufacturer that can take the order. Compare the cost of all the selected manufacturers for each order removed from Oi and choose the least cost order k and its manufacturer j.

Step 2: If the sum of the cost of orders from Ts after removing the order k, and the cost of order k manufactured by j is smaller than or equal to that of Ts, let Oi = Oi – {order k}, Ts = Ts - { (i, k) } + {(j,k)} and go to Step 1. Otherwise, go to Step 4.

Step 3: If Oi has only one order, go to Step 4.

Step 4: The Ts becomes a final solution.

We suppose in this problem that the branch and bound method knows all production costs, and so the cost tables are available by branch. <Figure 3> shows branch tables by combination of manufacturers and orders based on the <table 2>. However, in case of the branch and bound method, if the size of a problem becomes larger, its calculation time increases rapidly. Therefore, this method is not appropriate for the supply chain management that seeks an equal transaction opportunity among multiple business partners. In addition, it is different from the negotiation method in the sense that it cannot show the profit and loss of each manufacturer.

## 4. The negotiation method among manufacturers

### 4.1. Scenario

This study presents a concrete method as a solution to the supply chain formation problem by using agent negotiation based on a SET model. In particular, through information sharing, both internal and external factors are considered when making a decision. In addition, by capitalizing on agent negotiation, all members are rewarded simultaneously, consequently accelerating performance of the whole supply chain.

The negotiation method, which can be made by means of strategic alliances among manufacturers, will be used not only to minimize the production cost but also reduce the total cost of the whole supply chain. The negotiation method can be explained through a scenario as shown in the below <figure 4>.

The request of the estimates for order 1, order 2, and order 3 has been made to the three manufacturers - A, B, and C nearly at the same time. These orders’ delivery periods are tight, and these orders have respectively been placed by buyer 1, buyer 2, and buyer 3. All three orders have been placed nearly at the same time with a similar due date. Accordingly, joint scheduling for three orders has been made, and the simultaneous scheduling cost means the cost coming from this joint scheduling. However, due to the earliness cost and tardiness cost, the simultaneous cost for each order is much higher than each individual cost. When these production costs have been offered to the buyers, the order 1 has been placed with manufacturer A, and the order 2 and 3 with the manufacturer B, but no order has been placed with the manufacturer C. In this case, the manufacturer B has become to receive two definite orders. A definite order here means the order confirmed by a buyer.

An actual manufacturing cost is shown in the <figure 4>, and in case of the manufacturer B with whom two orders have been placed, its simultaneous scheduling cost for two orders is higher than the individual scheduling cost for each order, but lower than the simultaneous scheduling cost for three orders. The difference between the simultaneous scheduling cost and actual manufacturing cost has happened in case of manufacturer A and B, but the total of both actual manufacturing costs is 43, and this figure cannot reach the optimal solution for the whole supply chain.

At this point in time, the manufacturer B, who has two definite orders, begins to figure up whether it can produce more profit, if he subcontracts one order to the other manufacturer. To this end, he has to make a decision on what to subcontract and which subcontractor to choose. First of all, the manufacturer B asks the manufacturer A and B to subcontract for the order 2 (refer to No. 5 of the table 3). As a result of the subcontract estimation, in case of the manufacturer A, the simultaneous scheduling cost for the definite order 1 and the subcontract order 2 has been generated, thus increasing to 11 and 15 respectively. Accordingly, in case of the definite order 1, the cost has increased by 1 due to the simultaneous scheduling cost, and so to make up for this loss, he asks the manufacturer B for 16 instead of 15 (refer to No. 6 of the table 3).

Meanwhile, in case of the manufacturer C who has no definite order, he demands 15 for the order 2. Therefore, the manufacturer B makes a negotiation with the manufacturer C. In this case, the B’s profit increases by 2 through negotiation. When trying to subcontract the order 2, the manufacturing cost of the C is 15, and so it is the same with his actual manufacturing cost. But because he fulfills the definite order 3 individually, his profit increases by 2.

Finally, in case of subcontracting the order 3, as shown in the previous case, if he subcontracts to the manufacturer C, the C can fulfill the order at 14. In this case, the profit coming from the order 3 increases by 4. And also his profit increases by 1 from the definite order 2 due to the individual scheduling cost. So, his total profit increases to 5 (refer to No. 8 of the table 3). In conclusion, the manufacturer B decides to subcontract the order 3 to the manufacturer C. In this case, the total production cost for three orders is 38, thus achieving the minimum cost for the whole supply chain (refer to No. 9 of the table 3). Furthermore, all the participants make a profit from the negotiations (refer to No. 10 of the table 3).

### 4.2. Definition of negotiation factors and algorithm

The definition of the negotiation factors and algorithm based on the above scenario is as follows.

Definition of Negotiation Factors

Individual scheduling cost: this is the first scheduling cost when one order is placed with the manufacturer.

Simultaneous scheduling cost: this is the rescheduling cost when an additional order is placed with the manufacturer and so he needs the rescheduling as a group.

Definite order: the order that is placed with the manufacturer who has suggested the minimum price after the simultaneous scheduling.

Profit (income cost): this is the cost for a definite order. The manufacturer receives this production cost from the buyer.

Actual manufacturing cost: the production cost inputted by the manufacturer for order fulfillment.

Difference: a definite order will be suggested after simultaneous scheduling, but if the actual manufacturing cost of the definite order is smaller than the simultaneous scheduling cost, then the difference will take place (difference = income - actual manufacturing cost).

Lowest individual order: the order with the lowest cost among the individual scheduling cost by manufacturer.

Determination of a subcontract order: when there are more than two definite orders, and the manufacturer wants to decide which order to subcontract.

Selection of subcontractor: the negotiation leader is to select the subcontractor among the other manufacturers. The criteria is that the actual manufacturing cost of the subcontract candidate should be lower than that of the negotiation leader and also that if there are more than two subcontract candidates, the manufacturer with a lower actual manufacturing cost should be chosen.

The flow chart of the <figure 5> shows us a make-to-order production system between a buyer and a manufacturer and the process of an ordinary negotiation.

### 4.3. Optimization experiment

Based on the above-mentioned algorithm and scenario of the negotiation method, experiments have been made. The purpose of the experiment is to prove that the algorithm of this negotiation method can lead to the optimization of the supply chain. To this end, this test has used the program language C^{++}. Also the algorithm of the branch and bound method has been tested for a comparison with the negotiation method. The range of the experiment includes three manufacturers and four orders, and each individual scheduling cost has been coordinated for generation of a variety of negotiations.

The results of these experiments are shown from the <figure 6> to the <figure 9>. In the figures each individual scheduling cost has directly been inputted by the experimenter, and each simultaneous scheduling cost has been made to produce random numbers automatically, but not allowing the same order to produce the same random numbers.

According to the results of the scenario 1 experiment, the definite orders are as follows. The manufacturer 1 fulfills the order 1 and 2, the manufacturer 2 fulfills the order 4, and the manufacturer 3 fulfills the order 3. And the total manufacturing cost in this case is 33. After this, the subcontract negotiation has taken place twice, i.e. subcontract negotiation 1 and 2. Both subcontract negotiations have made the same profit of 1 respectively. Eventually the definite orders have been changed as follows.

Manufacturer 1: {order 1}, manufacturer 2: {order 4}, manufacturer 3: {order 2, order 3}: optimal value 32

Manufacturer 1: {order 2}, manufacturer 2: {order 4}, manufacturer 3: {order 1, order 3}: optimal value 32

The above results that come after the negotiations are forming a new supply chain, consequently generating the minimum value for the optimal supply chain formation. The same results are being generated in the other scenarios. The results of four scenarios have been summarized in the <table 4>

The optimal values from the above negotiation method have been the same as that of the branch and bound method. However, thanks to the limitation of the number of orders and manufacturers, both methods have generated their results nearly at the same time. As mentioned in chapter 3, in case of the branch and bound method, all the information on the simultaneous scheduling cost of each relevant manufacturer and order cost should be known. Therefore, if the number of manufacturers and orders increases, its calculation time increases rapidly. More importantly, the negotiation method can be made on a real-time basis, making it possible to figure out the profit and loss of negotiation, consequently improving the negotiators’ understanding.

## 5. Conclusion

Until now, the researches on the supply chain formation have focused on integrated scheduling mainly dealing with the integration of the vertical relationship. However, this paper has tried to consider the competitive environment of the member organizations having a horizontal relationship in an effort to expand the vertical relationship in the supply chain. Due to the excessively competitive environment, the diseconomies of scale are taking place, thus causing losses by producing below the marginal cost of a manufacturer.

However, a manufacturer tries to seek a cooperative relationship with other manufacturers to secure much more stable profit, and this effort leads to the origin of the negotiation method. Currently, in the free economy market the cooperative relationship develops into the strategic alliance, thus pursuing competitive superiority through this strategic alliance. As shown in the previous experiments, the negotiation method has contributed not only to making a profit for the participating manufacturers but also to bringing the optimal solution to the supply chain. Nevertheless, this study needs more efforts in the sense that the negotiation method has used a limited number of manufacturers and orders. Also we admit that this study has to apply a real case to this negotiation method. From now on more researches will be made on these problems.

## Acknowledgments

This work was supported by National Research Foundation of Korea- Grant funded by the Korean Government (KRF-2009-32A-B00090)