# Scheduling Auction: A New Manufacturing Business Model for Balancing Customization and Quick Delivery

Shota Suginouchi, Hajime Mizuyama

► To cite this version:

Shota Suginouchi, Hajime Mizuyama. Scheduling Auction: A New Manufacturing Business Model for Balancing Customization and Quick Delivery. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2019, Austin, TX, United States. pp.109-117, 10.1007/978-3-030-29996-5_13. hal-02460496

HAL Id: hal-02460496

https://inria.hal.science/hal-02460496

Submitted on 30 Jan 2020

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 Attribution 4.0 International License
# Scheduling Auction: A New Manufacturing Business Model for Balancing Customization and Quick Delivery

Shota Suginouchi[0000-0002-2377-1188] ✉ and
Hajime Mizuyama[0000-0001-9823-1832]

Aoyama Gakuin University, 5-10-1 Fuchinobe, Sagamihara, Kanagawa 252-5258, Japan

suginouchi@ise.aoyama.ac.jp

**Abstract.** This paper proposes a new manufacturing business model that is enabled by a novel scheduling method based on an auction, called *Scheduling Auction*. The proposed scheduling method and the associated business model aim to balance expanding customization and quick delivery to better satisfy customers. It accepts bids from customers, captures their preferences in terms of product type and due date more extensively than before from the bids and reflects those preferences in the production schedule. The fundamental framework of the method and its working are illustrated with a simple case of a factory with a single machine. Future research directions include conducting validation experiments with human subjects and extending the method to more complex production systems.

**Keywords:** Production Scheduling · Auction · Mechanism Design.

## 1 Introduction

Manufacturing companies must meet customers' demands. To satisfy diverse market demands, production styles have been continuously changed from high-volume low-variety production to low-volume high-variety production. This trend keeps increasing product variety, and yet the requested due dates never become longer. Thus, companies face a crucial challenge of how to balance expanding customization and quick delivery to satisfy their customers.

The conventional manufacturing business model can be broadly classified into make-to-stock (MTS) and make-to-order (MTO) models. MTS is characterized by a short lead-time from order to delivery, where quick delivery is accomplished in exchange for holding product inventory. Because the cost and risk associated with holding inventory increase with increasing product variety, naive MTS is not suitable for most extremely high-variety production environments currently in use. MTO, however, deals with high-variety production with minimal inventory, by making the production schedule after receiving orders. However, the resultant longer lead-time to delivery is not always accepted by the market. Mass
customization is a relatively new business model that combines MTO of final product assembly with MTS of standardized parts and units, thereby making the lead-time shorter than that of naive MTO with less inventory than naive MTS. However, demanding customers remain unsatisfied.

Thus, this paper proposes a new manufacturing business model that is en-
abled by a novel scheduling method based on an auction, called *Scheduling Auction*. The importance of scheduling is well recognized even in conventional MTO
and mass-customization, where the problem is captured as an efficient allocation
of jobs to machines along the time axis. The jobs considered here correspond to
a set of orders provided by customers, which specify product type and due date.
Thus, when zooming out back to each customer's perspective, another relevant
decision is made in advance by the customer in terms of which product type
and due date should be claimed. The proposed method is unique in that it deals
with these two decision problems simultaneously by involving customers in the
computational process, and it tries to obtain a production schedule preferable
to the customers.

In *Scheduling Auction*, customers are invited to join an auction and bid on a product type and due date. A schedule is then made according to the bids collected from the customers. In conventional production scheduling, an order from a customer is specified by a single set of values for the product type, price, and due date, e.g., "Product A, $100, and within two weeks". In the proposed method, in contrast, the preference of the customer can be expressed more flexibly, e.g., "I want to buy Product A or Product B but not both. Product A is better than Product B, if it is delivered until the end of this month." The flexibility expands the solution space of the corresponding scheduling problem, and is expected to lead to a superior solution. This paper presents the fundamental framework of *Scheduling Auction* by using a simple case of a factory with a single machine.

## 1.1 Literature Review

Some papers have proposed a production scheduling method based on an auction mechanism. For example, Kutanoglu and Wu [1] used a combinatorial auction and Lagrangean relaxation for scheduling. In this study, auctioned goods are the right to occupy a machine in a specified time slot. Each job is treated as an agent and bids for a combination of time slots for processing itself. The auctioneer coordinates the bids by adjusting the price of each time slot according to the conflicts among the bidders. The primary motivation behind these studies is how to solve a scheduling problem through distributed computation rather than how to capture and incorporate customers' detailed preference into the schedule.

Suginouchi et al. [2, 3] utilized a combinatorial auction for taking customers'
preferences into consideration in scheduling. This study addresses the schedul-
ing problem by repeating auctioning among computer agents representing cus-
tomers, which imitates a negotiation process among customers. A sub-optimal
solution for the corresponding combinatorial optimization problem is obtained
<figure><img src="image_2.png" /><figcaption>Fig. 1. Schema of *Scheduling Auction*</figcaption></figure>

by a math-heuristic approach [4]. To more accurately capture customers' preference, it is desirable to have the actual customers participate in the negotiation process. However, it is not realistic for actual customers to follow the troublesome process of repeating an auction many times. Furthermore, strategic interaction among the customers needs to be properly managed to involve them into the computational process.

Mechanism design is an academic field addressing strategic interactions among self-interested agents, and it has recently started to be applied to production scheduling [5–7]. Most studies in this field focus on the theoretical aspect and deal with simplified settings, where either machines or jobs are simply deemed as self-interested agents, and the earlier decision of having customers choose product type and due date is not incorporated. There have also been some initial application studies. For example, Zhong et al.[8] and Zheng et al. [9] applied the auction-based scheduling method to energy hub and service clouds, respectively. Nishino et al. [10] proposed an auction mechanism for arranging seat reservations in a movie theater. However, all the settings considered in these studies are different from the one for *Scheduling Auction*.

## 2 Proposed Method

It is assumed that a manufacturing company divides a planning horizon into multiple terms, and holds an auction to plan the production schedule of every term. This paper focuses on an auction held for a certain term. The term is further divided into smaller time units, and due dates, processing times, completion times, etc., are all specified in terms of the units in the following.
Fig. 1 shows a schema of the proposed method, *Scheduling Auction*. The manufacturing company takes the role of the auctioneer, and customers are treated as bidders. Auctioned goods are not products but combinations of product type and due date. The customers' preference of the goods is assumed to be quasi-linear.

There are some bidders, and each bidder may submit multiple bids for different combinations of product type and due date. When two or more bids are submitted by a bidder, only one of them can be assigned to the schedule. Because the production capacity is limited, not all customers can receive a product. If all bids made by a customer are not chosen by the auction, the customer may join the next-term auction or give up obtaining a product.

When bids are collected, then the auctioneer determines the winning bids among them and establishes the corresponding production schedule. The criterion of this winner determination is to maximize the social surplus. The contract price is determined by using the Vickrey-Clarke-Groves (VCG) mechanism [11–13], to induce truthful behavior of the bidders.

# 3 Example Case

In this section, a single-machine scheduling problem is used to illustrate the working of the proposed method.

## 3.1 Notation

* $i$ : Customer (Bidder) ($i = 1, \dots, I$)

* $t$ : Product type ($t = 1, \dots, T$)

* $PT_t$ : Processing time of type $t$

* $d$ : Index of possible due dates ($d = 1, \dots, D$)

* $DD_d$ : Due date corresponding to index $d$

* $b_{i,t,d}$ : Customer $i$'s bid value on type $t$ and due date index $d$

* $p_i$ : Customer $i$'s payment

* $x_{i,t,d} \in \{0,1\}$ : A decision variable indicating whether $b_{i,t,d}$ is accepted

* $j$ : Job processed in the $j$th ($j = 1, \dots, I$)

* $jn_j$ : The customer ordering the product corresponding to job $j$ (Decision variable)

* $CO_j$ : Completion time of job $j$

* $PO_j$ : Processing time of job $j$

* $DO_j$ : Due date of job $j$

* $SS$ : Social surplus

* $SS_i$ : Social surplus in the absence of customer $i$

## 3.2 Formulation

The following formulation specifies the problem of optimizing the production schedule and determining winners of the auction at the same time.
$$ \max \sum_{i=1}^{I} \sum_{t=1}^{T} \sum_{d=1}^{D} b_{i,t,d} \times x_{i,t,d} \qquad (1) $$

$$ CO_j = \begin{cases} PO_j & (\text{if } j = 1) \\ CO_{j-1} + PO_j & (\text{otherwise}) \end{cases} \qquad (\forall j) \qquad (2) $$

$$ DO_j = \sum_{t=1}^{T} \sum_{d=1}^{D} DD_d \times x_{jn_j,t,d} \qquad (\forall j) \qquad (3) $$

$$ \text{s.t.} \quad CO_j \leq DO_j \qquad (\forall j) \qquad (4) $$

$$ jn_j \neq jn_{j'} \qquad (\forall j, \forall j' | j \neq j') \qquad (5) $$

$$ PO_j = \sum_{t=1}^{T} \sum_{d=1}^{D} PT_t \times x_{jn_j,t,d} \qquad (\forall j) \qquad (6) $$

$$ \sum_{t=1}^{T} \sum_{d=1}^{D} x_{i,t,d} = 1 \qquad (\forall i) \qquad (7) $$

$$ jn_j \in \{1, \dots, J\} \qquad (\forall j) \qquad (8) $$

$$ x_{i,t,d} \in \{0, 1\} \qquad (9) $$

The objective function is expressed by Equation (1), which maximizes the sum of the accepted bid values. Equation (2) defines the completion time $CO_j$ of job j. Equation (3) defines the due date $DO_j$ of job j. Equation (4) guarantees that job j completes before its due date $DO_j$. Equation (5) guarantees that job j is processed only once. Equation (6) expresses that the processing time of job j is determined by the product type t chosen by customer $jn_j$. Equation (7) guarantees that the product type t and due date $DD_d$ of customer i are determined uniquely.

## 3.3 Algorithm

In the case of the single-machine scheduling problem, the algorithm of Scheduling Auction is as follows:

**STEP 1** Customers who want to order a product participate in the auction as bidders. Each bidder may bid for all combinations of product type t and due date $DD_d$. Table 1 shows an example of such bids, where the number of product types T is three and the number of possible due dates D is two.

**STEP 2** The auctioneer gathers bids and solves the integer optimization problem formulated in section 3.2 to determine the winning bids and to plan a production schedule. The social surplus SS is also obtained.

**STEP 3** The auctioneer determines each bidder's payment $p_i$ using the VCG mechanism [11–13]. To do so, i is initialized to be 1.
<table><caption>**Table 1.** An Example of Bids</caption><thead><tr><th rowspan="2">Due date DD<sub>d</sub></th><th colspan="3">Product type t</th></tr><tr><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><td>DD<sub>1</sub></td><td>$200</td><td>$100</td><td>$50</td></tr><tr><td>DD<sub>2</sub></td><td>$150</td><td>$100</td><td>$0</td></tr></tbody></table>

<table><caption>**Table 2.** Experimental Conditions</caption><tr><td>Number of customers I 5, 10</td><td>Bid value b<sub>i,t,1</sub></td><td>$U[1, 100]*</td></tr><tr><td>Number of types T 2, 10</td><td>Bid value b<sub>i,t,d</sub>(d ≥ 2)</td><td>max{U[1, 100], b<sub>i,t,d-1</sub>}</td></tr><tr><td>Number of possible due dates D 2, 10</td><td>Processing time PT<sub>t</sub></td><td>t</td></tr><tr><td>Number of trials 10</td><td>Due date DD<sub>d</sub></td><td>ceil{(d + 1) × <sup>T×I</sup>⁄<sub>D</sub>} **</td></tr></table>

**STEP 4** The auctioneer calculates the social surplus $SS_{-i}$ in the absence of customer $i$ by solving the integer optimization problem formulated in section 3.2. Equation (10) determines customer $i$'s payment $p_i$.

$$p_i = SS_{-i} - \left( SS - \sum_{t=1}^{T} \sum_{d=1}^{D} b_{i,t,d} \times x_{i,t,d} \right) \quad (10)$$

**STEP 5** If $i \neq I$, $i := i+1$ and go to **STEP 4**. Otherwise, the auctioneer ends the auction.

## 3.4 Computational Experiments

To discuss the performance of *Scheduling Auction*, numerical experiments were conducted. The experiments were performed with the conditions shown in Table 2. This study used a CPLEX 12.6.3 [14] and Inter(R) Core i7 3.50GHZ 16.0GB memory computer.

Fig. 2 shows a schedule obtained by *Scheduling Auction* when the number of customers $I$ is 5, the number of product types $T$ is 2, and the number of possible due dates $D$ is 2. The objective function value corresponding to the social surplus is $336. Table 3 shows the bid values. * signifies accepted bids. In this case, customer 1 pays $5, customer 2 pays $29, customer 3 pays $29, customer 4 pays $0, and customer 5 pays $19.

The mean calculation time for solving a problem was 0.03 s in 10 trials. The calculation time increased exponentially as the number of customers $I$, the number of product types $T$, and the number of possible due dates $D$ increased. For example, the mean calculation time was 22.02 s in 10 trials when $I = 10$, $T = 2$ and $D = 2$. When $I = 10$, $T = 2$, and $D = 10$, the mean calculation time for solving optimizing a problem was 96.06 s in 10 trials. When $I = 10$, $T = 10$, and $D = 2$, the mean calculation time was 180.58 s in 10 trials. The exact solution cannot be obtained in cases where $I$ is more than 15.

<footnote>* $U[a, b]$; random sampling from a uniform distribution</footnote>

<footnote>** ceil($x$): roundup integer</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 2. Example of an Obtained Schedule ($I = 5, T = 2, D = 2$)</figcaption></figure>

<table><caption>Table 3. Each Bidder's Bid Values</caption><thead><tr><th rowspan="2">Customer i</th><th>t = 1</th><th>t = 1</th><th>t = 2</th><th>t = 2</th></tr><tr><th>d = 1</th><th>d = 2</th><th>d = 1</th><th>d = 2</th></tr></thead><tbody><tr><td>1</td><td>*79</td><td>11</td><td>42</td><td>2</td></tr><tr><td>2</td><td>40</td><td>40</td><td>*73</td><td>6</td></tr><tr><td>3</td><td>19</td><td>13</td><td>*97</td><td>41</td></tr><tr><td>4</td><td>34</td><td>8</td><td>43</td><td>*29</td></tr><tr><td>5</td><td>58</td><td>*58</td><td>87</td><td>40</td></tr></tbody></table>

Furthermore, to decide each customer's payment, the auctioneer must solve the integer optimization problem shown in section 3.2 ($I + 1$) times. Thus, an efficient optimization method is required to realize *Scheduling Auction*.

# 4 Conclusion

This paper proposes an auction-based scheduling method and a new manufacturing business model enabled by the method. The proposed method captures customers' preferences in terms of product type and due date more extensively than before from their bids, which is then reflected in to the production schedule. A winner determination procedure is also presented.

This paper uses a simple case of only one machine to describe the fundamental framework of the proposed scheduling method and the associated business model. Future research directions include conducting experiments with computer agents and/or human subjects and extending the problem formulation and solution procedure to more complex production systems.

Furthermore, this paper implicitly assumes that customers' preferences are determined only by the characteristics of the final product, such as specification, price, and due date. In the future, however, customers may also care about how the product is produced, i.e., the production process itself. A typical example is observed in the liberalized energy market. In April 2006, the retail electricity market in Japan was liberalized, and consumers were enabled to select a retailer. Consumers' selection criteria were found out to include not only the price but also the greenness, etc. Some retailers started to appeal to consumers by the method of generating electricity, e.g. their energy was not generated from nuclear power plants but from renewable energy sources, etc. Thus, future customers may have
a preference in terms of the energy utilized to produce a product, and such a preference could also be incorporated into the production schedule by extending the method proposed in this paper.

**Acknowledgements** This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Young Scientists, 2019-2022 (19K15240, Shota Suginouchi).

## References

1. Kutanoglu, E., and Wu, S. D.: On combinatorial auction and Lagrangean relaxation for Distributed Resource scheduling, IIE Transactions. vol. 31, issue 9, pp. 813–826 (1999) doi: 0.1023/A:1007666414678

2. Suginouchi, S., Kokuryo, D., and Kaihara, T.: Value co-creative manufacturing system for mass customization: Concept of smart factory and operations method using autonomous negotiation mechanism. Proceedings of the 50th CIRP Conference on Manufacturing Systems (USB) (2017) doi: 10.1016/j.procir.2017.03.313

3. Suginouchi, S., Kaihara, T., Fujii, N., and Kokuryo, D.: Utilization of pheromone in production scheduling by negotiation and cooperation among customers. Proceedings of SICE Annual Conference 2018, pp. 73–778 (2018) doi: 10.23919/SICE.2018.8492625

4. Boschetti, M., Maniezzo, V., Roffilli, M., and Rohler, A. B.: Matheuristics: Optimization, simulation and control. International Workshop on Hybrid Metaheuristics, pp. 171–177 (2009) doi:10.1007/978-3-642-04918-7_13

5. Heydenreich, B., Mller, R., and Uetz, M.: Games and Mechanism design in machine scheduling - An introduction. Production and Operations Management, vol. 16, no. 4 pp. 437-454, (2007) doi: 10.1111/j.1937-5956.2007.tb00271.x

6. Christodoulou, G., and Koutsoupias, E.: Mechanism design for scheduling. Bulletin of the EATCS, no. 97, pp. 40–59 (2009)

7. Kress, D., Meiswinkel, S., and Pesch, E.: Mechanism design for machine scheduling problems: Classification and literature overview, OR Spectrum, vol. 40, pp. 583–611, (2018) doi: 10.1007/s00291-018-0512-8

8. Zhong, W., Yang, C., Xie, K., Xie, S., and Zhang, Y.: ADMM-based distributed auction mechanism for energy hub scheduling in smart buildings, IEEE Access, vol. 6, pp. 45635–45645 (2018) doi: 10.1109/ACCESS.2018.2865625

9. Zheng, B., Li, P., and Liu, S.: Mechanisms for optimally scheduling and pricing pleasingly parallel jobs in service clouds, IEEE Access, vol. 6, pp. 73733-73749 (2018) doi: 10.1109/ACCESS.2018.2882605

10. Nishino, N., Fukuya, K., and Ueda, K.: An auction mechanism considering seat reservations in movie theater services, International Journal of Organizational and Collective Intelligence (IJOCI). vol. 2, issue 1, pp. 63–76 (2011) doi: 10.4018/joci.2011010104

11. Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders, The Journal of Finance, vol. 16, no. 1, pp. 8–37 (1961) doi: 10.2307/2977633

12. Clarke, E. H.: Multipart pricing of public goods, Public Choice, vol. 11, issue 1, pp. 17-33 (1971) doi: 10.1007/BF01726210

13. Groves, T.: Incentives in Teams, Econometrica, vol. 41, no. 4, pp. 617-631 (1973) doi: 10.2307/1914085

14. IBM Web page. https://www.ibm.com/analytics/data-science/prescriptive-analytics/cplex-optimizer