A Multi-Customer Supply Chain Scheduling with Subcontracting Option on a Single Machine

Xiaoping Ou, Fei Luo^*

College of Mathematics and Statistics, Sichuan University of Science and Engineering, Zigong, China.

DOI: 10.4236/jamp.2022.1012249                

Abstract

This paper studies the cost problem caused by the activity of the work-piece in the supply chain. The objective function is to find an optimal ordering that minimizes the total cost of production, transportation and subcontracting. This paper presents a dynamic programming algorithm for the corresponding sorting problem, and finally demonstrates the feasibility of the algorithm through an example.

Keywords

Supply Chain Scheduling, Singe-Machine, Dynamic Programming Algorithm

1. Introduction

Before the goods reach consumers, the main process of business connection of all stakeholders is as follows: raw materials are firstly purchased, then products are made, and finally the products are delivered to consumers by the sales network. The seamless integration process of suppliers, manufacturers, distributors, retailers and end users formed a network chain structure known as the supply chain. The practical significance of supply chain and its research value have attracted the wide attention of supply chain management researchers. In [1], wang et al. studied supply chain scheduling with learning effects and considered the four main objective functions in the sequencing theory. In which multiple customers are distributed in different locations. Each customer has a certain number of workpieces to be processed by the manufacturer, and the workpieces need to be transported to the corresponding customers after the production is completed. In [2], Alessandro et al. studied the supply chain sequencing of one supplier and multiple manufacturers and the optimal sequencing of suppliers and manufacturers and the minimal total cost of the common optimal sequencing of suppliers and manufacturers, and further proposed a polynomial algorithm. In [3], Chen et al. studied the case with different transportation modes, and proved that the problem was strongly NP hard when the objective function is the sum of weighted total completion time and distribution cost in general, and given the optimal algorithm for some special cases. In [4], Averbakh et al. studied the sequencing problem of online supply chain. Since the work is published online, the manufacturer has no idea about the situation of the workpiece to be processed. Because preemption is allowed, the processing work can be delivered in batches. The author considered the cases of one customer and multiple customers respectively, aiming to minimize the total cost, and giving the optimal competitive ratio of the algorithm. The model in [1] [3] [4] was a two-layer supply chain without raw material suppliers, while the considered model in [2] was a two-layer supply chain without retailers.

The works in above literatures all only consider the situation of two-layer supply chain. In recent years, the two-layer supply chain has been studied deeply. However, there are few researches on the three-layer supply chain. The three-layer supply chain sequencing problem including suppliers, manufacturers and retailers was investigated in [5]. In this model, there is one supplier, multiple manufacturers and multiple retailers. Suppliers transport raw materials to multiple manufacturers, and manufacturers transport finished products to multiple customers, aiming to minimize the sequencing and distribution costs of the entire supply chain. In [6], Nikandish et al. investigated the minimal sum of the three cost factors for one supplier, multiple manufacturers and multiple retailers by considering a three-layer supply chain of one supplier, multiple manufacturers and multiple retailers. In [7], Dawande et al. investigated a three-layer supply chain sequencing problem composed of manufacturers, distributors and customers, and further discussed two practical problems and provided an algorithm for each problem. Manufacturers and distributors each have an optimal sequencing, but these two sequencings are often inconsistent, which has a negative impact on the whole supply chain. In [8], Selvarajah and Zhang investigated the issue of outsourcing supply chain. In [9], Liu and Zhang investigated the ordering model of supply chain with machine learning effect and gave a model of multi-customer distribution. In this model, the learning effect occurs when the workpiece is processed on the machine, and the actual processing time of the workpiece is a minus function of its position. In [10], Yang and Chen investigated a classical single machine scheduling problem but with uncertainty. A robust optimization model is presented, and an effective deep cut is derived. Numerical experiments show effectiveness of the derived cut. Lu et al. [11] studied the scheduling problem of time limit assignment with work-piece learning effect and convex resource allocation. They pointed out that one conclusion in [12] was wrong and gave a correct conclusion. The customer needs to accept its corresponding completed work pieces. After the completion of each batch of work pieces, they need to be distributed, but the distribution will take some time and expense. Since a large number of customers need distribution, in order to save resources as much as possible and reduce the number of trains and transport times, transport vehicles should load as much goods as possible before starting transport. In the case that there are no more than two customers in a transport vehicle, the objective function of the study is to minimize the total process time and minimize the maximum delay time, and the corresponding dynamic programming algorithms are given for these two problems respectively. On this basis, this paper simplifies the content and deepens the structure. We omit the learning effect of the machine, increase the supply and transportation of raw materials, break the limit of no more than two customers for the loading of customer materials, and specify the transportation process and details. We also use the dynamic programming method for research. But we’re not going to look at minimizing the total time.

This paper mainly studies the sequencing problem of multi-customer single-machine supply chain considering subcontracting. Under the premise of single-machine, multi-customer and multi-material supplier is allowed to subcontract. The objective function is the minimum total cost of production, transportation and subcontracting. The dynamic programming algorithm is proposed and the feasibility of the algorithm is verified by an example.

2. Problem Formulation

The model studied in this paper is described as follows.

A manufacturer gets n orders from customers in different locations at time zero moment. The order set, in which the orders correspond the raw material manufactures. The manufacturer has only one machine to process these orders. Only when all the raw materials required by the customer arrive at the processing plant, the customer’s order is allowed to be processed. The customer is called the permitted processing customer. After the order is completed on the machine, it needs to be transported to the corresponding customer. The manufacturer has enough transporters, in which each transporter can mix load the work-piece of different customers and the raw materials needed for production. The capacity of each transporter is a constant and the transportation cost is related to its transportation distance. In addition, all orders can be subcontracted, which requires the subcontractor to purchase raw materials, and further manufacture and transport them to the customer. The goal of this paper is to find an integrated solution that minimizes the total cost of production, shipping, and subcontracting.

The symbols are described as follows:

$n_i$ : Number of work-pieces to be processed for order i.

$n_i^{\mathrm{<mo>\; *\; </mo>}}$ : Number of units of raw material required for order i.

N: A set of all orders.

$N^{\mathrm{<mo>\; *\; </mo>}}$ : A set of unsubcontracted orders.

$N\backslash N^{\mathrm{<mo>\; *\; </mo>}}$ : A set of subcontracted orders.

$f_i$ : Transportation cost of order i, namely, the sum of both the transportation cost of the raw materials of the order and the transportation cost of the order to the customer. $k_i$ : Subcontracting cost of order i.

$p_i$ : Production cost of order i.

$x_i=1$ : Order i is not subcontracted.

$x_i=0$ : Order i is subcontracted.

$S_i$ : Transportation costs of the raw materials from the plant to manufacturer for customer i.

${S^{\prime }}_i$ : The cost of transportation for the carriage carrying part $n_i-\lfloor \frac{n_i}{b}\rfloor \cdot b$ of customer i from the customer’s raw material plant through certain customer’s raw material plant until it returns to the manufacturer’s premises.

$S_{i\mathrm{,}j}$ : The transportation cost of the transporter from Customer i’s raw material plant to Customer j’s raw material plant.

$s_i$ : The cost of transporting for an order from the manufacturer to customer i.

${s^{\prime }}_i$ : The cost of transporting from the manufacturer to certain customers and finally to customer i.

$s_{i\mathrm{,}j}$ : The cost of transporting from Customer i to Customer j.

Definition 2.1 The transportation cost of order without subcontracting is:

$\begin{array}{c}{f}_i=2\lfloor \frac{n_i^{*}}{b}\rfloor \cdot S_i+\left[\left(\lceil \frac{n_i^{*}}{b}\rceil -\lfloor \frac{n_i^{*}}{b}\rfloor \right)\cdot {S^{\prime }}_i+\left(\lceil \frac{n_i^{*}}{b}\rceil -\lfloor \frac{n_i^{*}}{b}\rfloor \right)\cdot S_i\right]\\ +\lfloor \frac{n_i^{*}}{b}\rfloor s_i+\left(\lceil \frac{n_i^{*}}{b}\rceil -\lfloor \frac{n_i^{*}}{b}\rfloor \right)\cdot {s^{\prime }}_i,\end{array}$ (2.1)

where $2\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor$ represents the cost of transporting both from manufacturer to the raw materials plant of customer i and the part of the vehicle full of raw materials return to the manufacturer; $\left(\lceil \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rceil -\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \right)\cdot {S^{\prime }}_i+\left(\lceil \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rceil -\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \right)\cdot S_i$ represents the cost of transporting both from the manufacturer to the raw materials plant of customer i, then through other customer raw material for less than one load of raw materials, and finally back to the manufacturer; $\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \cdot s_i$ represents the cost for the transporting for the completed work-pieces of the full vehicle from the manufacturer to customer i; $\left(\lceil \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rceil -\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \right)\cdot {s^{\prime }}_i$ represents the cost of transporting for less than one load of completed work-pieces from the manufacturer through some customers to customer i.

Theorem 2.1 $f_s=min\left(f_1\mathrm{,}{f}_2\mathrm{,}{f}_3\right)$ is the optimal total transportation cost of transporting raw materials required for multiple orders to the manufacturer when order i is not subcontracted.

Proof: 1) The case for only two customers, the amount time of arriving the customer is shown in Figure 1. If the raw material $n_i^{\mathrm{<mo>\; *\; </mo>}}-\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \cdot b$ and $n_j^{\mathrm{<mo>\; *\; </mo>}}-\lfloor \frac{n_j^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \cdot b$ of customer i and j are transported separately, the total cost of the two customers is

Figure 1. The amount time of arriving the two customers.

$f_1=S_i+S_j\mathrm{.}$ (2.2)

If the raw material $n_i^{\mathrm{<mo>\; *\; </mo>}}-\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \cdot b$ and $n_j^{\mathrm{<mo>\; *\; </mo>}}-\lfloor \frac{n_j^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \cdot b$ of customer i and j are transported together, the total cost of the two customers is

$f_2=S_{i\mathrm{,}j}+min\left(S_1\mathrm{,}{S}_2\right)\mathrm{.}$ (2.3)

For the case, $f_3=0$.

2) The case for more than two customers, the amount time of arriving the customer is shown in Figure 2. If $n_i^{\mathrm{<mo>\; *\; </mo>}}-\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \cdot b$ is transported separately, the cost is

$f_1={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{S}_i.$ (2.4)

If $n_i^{\mathrm{<mo>\; *\; </mo>}}-\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \cdot b$ is transported together, the cost is

$f_2={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{S}_{i,i+1}+\min \left({\displaystyle \underset{i=1}{\overset{n}{\sum }}}{S}_i\right).$ (2.5)

If $n_i^{\mathrm{<mo>\; *\; </mo>}}-\lfloor \frac{n_i^{\mathrm{<mo>\; *\; </mo>}}}{b}\rfloor \cdot b$ is transported mixed, the cost is

$\begin{array}{c}{f}_3={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{S}_{i,i+1}-{\displaystyle \underset{k=1}{\overset{n-1}{\sum }}}\left(S_{k-1,k}+S_{k,k+1}\right)+{\displaystyle \underset{k=1}{\overset{n-1}{\sum }}}{S}_{k-1,k+1}\\ +\min \left({\displaystyle \underset{i=1}{\overset{n}{\sum }}}{S}_i-{\displaystyle \underset{k=1}{\overset{n}{\sum }}}{S}_k\right)+{\displaystyle \underset{k=1}{\overset{n}{\sum }}}{S}_k,\end{array}$ (2.6)

where ${\displaystyle {\sum }_{k=1}^n}{S}_K$ represent the transportation separately for the k raw material plant. If $k=1$, then $S_{k-1,k}=S_{0,1}=0$. If $k=n$, then $S_{k,k+1}=S_{n,n+1}=0$. So it is easy to obtain $S_{k-\mathrm{1,}k}\le S_{k-\mathrm{1,}k}+S_{k\mathrm{,}k+1}$. At last, the optimal transportation scheme can be obtained by iterative method.

Remark 2.1 When $f_s=min\left(f_1\mathrm{,}{f}_2\mathrm{,}{f}_3\right)$ does not subcontract corresponding to order i, the optimal total transportation cost of transporting completed parts from multiple orders to corresponding customers can be obtained by Theorem

Figure 2. The amount time of arriving the multiple customers.

2.1.

In order to better study the subcontracting of the order q, we give the definition $A_q$ and $B_q$. $A_q$ : The sum of both the production cost and transportation of the non-subcontracted sets for including the order q and the transportation of the subcontracted sets for excluding the order q. $B_q$ : The sum of both the production cost and transportation cost of the non-subcontracted order sets for excluding the order q and the subcontracted cost of the subcontracted order sets for including the order q.

Theorem 2.2 If $p_q{x}_q-k_q+\left(\min {\displaystyle {\sum }_{i\in N^{*}}}{f}_i{x}_i-\min {\displaystyle {\sum }_{i\in N^{*}\backslash q}}{f}_i{x}_i\right)>0$ or $p_q{x}_q+f_q{x}_q-k_{q>0}$, then the order q is subcontracted.

Proof: Since the subcontracting situation of order q has an impact on the processing and transportation of the subcontracted order set, it is divided into the following two types for discussion.

Case 1: Each truck just loads one customer’s raw materials and orders. In this case, we can get:

$A_q={\displaystyle \underset{i\in N^{*}}{\sum }}{p}_i{x}_i+{\displaystyle \underset{i\in N^{*}}{\sum }}{f}_i{x}_i+{\displaystyle \underset{j\in N\backslash N^{*}}{\sum }}{k}_j,$ (2.7)

$B_q={\displaystyle \underset{i\in N^{*}\backslash q}{\sum }}{p}_i{x}_i+{\displaystyle \underset{i\in N^{*}\backslash q}{\sum }}{f}_i{x}_i+{\displaystyle \underset{j\in N\backslash N^{*}+q}{\sum }}{k}_j.$ (2.8)

Since $A_q-B_q=p_q{x}_q+f_q{x}_q+f_q{x}_q-k_q$, if $A_q>B_q$, then the order q is subcontracted and the total cost is reduced.

Case 2: Not every truck just happens to carry one customer’s raw materials and orders. In this case, we can get:

$A_q={\displaystyle \underset{i\in N^{*}}{\sum }}{p}_i{x}_i+\min {\displaystyle \underset{i\in N^{*}}{\sum }}{f}_i{x}_i+{\displaystyle \underset{j\in N\backslash N^{*}}{\sum }}{k}_j,$ (2.9)

$B_q={\displaystyle \underset{i\in N^{*}\backslash q}{\sum }}{p}_i{x}_i+\min {\displaystyle \underset{i\in N^{*}\backslash q}{\sum }}{f}_i{x}_i+{\displaystyle \underset{j\in N\backslash N^{*}+q}{\sum }}{k}_j.$ (2.10)

Since $A_q-B_q=p_q{x}_q-k_q+\left(\min {\displaystyle {\sum }_{i\in N^{*}}}{f}_i{x}_i-\min {\displaystyle {\sum }_{i\in N^{*}\backslash q}}{f}_i{x}_i\right)$ and the inequity $A_q>B_q$, we can obtain that

$p_q{x}_q-k_q+\left(\min {\displaystyle {\sum }_{i\in N^{*}}}{f}_i{x}_i-\min {\displaystyle {\sum }_{i\in N^{*}\backslash q}}{f}_i{x}_i\right)>0$. Then the order q is subcontracted and the total cost is reduced.

3. Model and Algorithm Design

The mathematical model can be expressed as follows:

$\min \left({\displaystyle \underset{i\in N}{\sum }}{p}_i{x}_i+{\displaystyle \underset{i\in N}{\sum }}{f}_i{x}_i+{\displaystyle \underset{i\in N}{\sum }}{k}_i\left(1-x_i\right)\right).$

This part mainly considers that there are n customers and n material suppliers under the premise of single machine, and the workpiece of each customer is allowed to be subcontracted. In order to minimize the total cost of the single machine production, transportation of both raw materials and processed workpiece and subcontracting in the three-layer supply chain, we will divide it into the following five steps:

Step 1: Let $N^{\mathrm{<mo>\; *\; </mo>}}$ be the set of orders that are not subcontracted, and $N\backslash N^{\mathrm{<mo>\; *\; </mo>}}$ is the set of orders that are subcontracted. Place all orders in $N^{\mathrm{<mo>\; *\; </mo>}}$, in which $N\backslash N^{\mathrm{<mo>\; *\; </mo>}}$ is the empty set.

Step 2: The optimal transportation scheduling scheme formed by Definition 2.1, Theorem 2.1 and Remark 2.1 is denoted as $\delta$. Enumerate $\delta$ and mark the value after each enumeration scheme as $A_i\mathrm{,}i\in \mathrm{1,}\cdots {\mathrm{,2}}^n$, then further find the smallest value and mark it as $F_1$, that is $F_1=\min {\displaystyle {\sum }_{i=1}^{2^n}}{A}_i$, and mark the subcontract scheme as $V_1$.

Step 3: Randomly draw an order i from $N^{\mathrm{<mo>\; *\; </mo>}}$ and put it into $N\backslash N^{\mathrm{<mo>\; *\; </mo>}}$. Repeat Step 2 to get ${F^{\prime }}_1$ and ${V^{\prime }}_1$.

Step 4: Define $F\left(1\right)=\min \left(F_1,{F^{\prime }}_1\right)$. The subcontracting scheme corresponding to $\min \left(F_1,{F^{\prime }}_1\right)$ is denoted as ${\epsilon }_1$.

Step 5: Repeat the above steps to find out $F\left(i\right)\mathrm{,}i=\mathrm{1,}\cdots \mathrm{,}n$, and compare the objective function $F=\min {\displaystyle {\sum }_{i=1}^n}F\left(i\right)$, where F corresponds to ${\epsilon }_i$ as the final subcontracting scheme.

Example: The related information about customers, production costs and subcontracting costs are given in Table 1.

In the following, we will give some definitions for some basic values.

The transportation costs of the raw of custom i and j, from the raw materials plant to manufacturers, are $S_i=2$ and $S_j=3$ respectively. The transportation costs of an order, from the manufacturer to customer i and j, are $s_i=s_j=2$. The production costs of order i and j are $p_i=5$ and $p_j=7$ respectively. The subcontracting costs of order i and j are $k_i=k_j=11$.

In the following, we give some specific schemes to calculate the cost.

Scheme 1: If the order of customers i and j is not subcontracted, then the minimum total cost is $F_1=S_i+p_i+s_i+S_j+p_j+s_j=2+5+2+3+7+2=21$.

Scheme 2: If the order of customers i is subcontracted, but customer j is not, then the minimum total cost is $F_2=k_i+S_j+p_j+s_j=11+3+7+2=23$.

Scheme 3: If the order of customers j is subcontracted, but customer i is not, then the minimum total cost is $F_3=S_i+p_i+s_i+k_j=2+5+2+11=20$.

Table 1. The information for customer and cost.

Scheme 4: If the order of both customers i and j is subcontracted, then the minimum total cost is $F_4=k_i+k_j=11+11=22$.

From $F=\min {\displaystyle {\sum }_{i=1}^n}F\left(i\right)$, it is easy to obtain $F=\min \left(F_1,F_2,F_3,F_4\right)=F_3=20$.

4. Conclusion

This paper considers the single machine problem to find an integrated solution to minimize the total cost of production, transportation and subcontracting. Through the integrated analysis of the work-piece transportation, production and subcontracting, the optimal sorting of the objective function is found, and the corresponding dynamic programming algorithm is given. In the future, when each customer order requires $i_i$ raw materials and they are distributed in different regions, other objective functions, such as total loss of work lost, total weighted loss of advance, etc., can also be applied to the parallel machine or flow shop.

Funding

This work is supported by the Opening Project of Sichuan Province University Key Laboratory of Bridge Non-destruction Detecting and Engineering Computing (Grant No. 2022QZJ02, No. 2021QYJ07).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Wang, L., Zhang, Y. and Wang, C. (2013) Supply Chain Scheduling with Learning Effects. Journal of Systems Science and Mathematical Sciences, 33, 799-806.
[2]	Alessandro, A., Hall, N.G. and Pacciarelli, D. (2006) Supply Chain Scheduling: Sequence Coordination. Discrete Applied Mathematics, 154, 2044-2063. https://doi.org/10.1016/j.dam.2005.04.019
[3]	Chen, B. and Lee, C.-Y. (2008) Logistics Scheduling with Batching and Transportation. European Journal of Operation Research, 189, 871-876. https://doi.org/10.1016/j.ejor.2006.11.047
[4]	Averbakh, I. and Xue, Z. (2007) On-Line Supply Chain Scheduling Problems with Preemption. European Journal of Operational Research, 181, 500-504. https://doi.org/10.1016/j.ejor.2006.06.004
[5]	Hall, N.G. and Potts, C.N. (2003) Supply Chain Scheduling: Batching and Delivery. Operations Research, 51, 566-584. https://doi.org/10.1287/opre.51.4.566.16106
[6]	Nikandish, N., Eshghi, K. and Torabi, S.A. (2009) Integrated Procurement, Production and Delivery Scheduling in a Generalized three Stage Supply Chain. Journal of Industrial and Systems Engineering, 3, 189-212.
[7]	Dawande, M., Geismar, H.N., Hall, N.G. and Sriskandarajah, C. (2006) Supply Chain Scheduling: Distribution Systems. Production and Operations Management, 15, 243-261. https://doi.org/10.1111/j.1937-5956.2006.tb00243.x
[8]	Selvarajah, E. and Zhang, R. (2014) Supply Chain Scheduling to Minimize Holding Costs with Outsourcing. Annals of Operations Research, 217, 479-490. https://doi.org/10.1007/s10479-013-1522-1
[9]	Liu, Y. and Zhang, X. (2015) The Supply Chain Scheduling with Learning Effect and Muti-Customers Distribution. Journal of Chongqing Normal University (Natural Science), 32, 19-25.
[10]	Yang, F. and Chen, S. (2015) Deep Cutting Plane Inequalities for Stochastic Non-Preemptive Single Machine Scheduling Problem. American Journal of Operations Research, 5, 69-76. https://doi.org/10.4236/ajor.2015.52006
[11]	Lu, Y.-Y., Wang, T.-T., Wang, R.-Q. and Li, Y. (2021) A Note on Due-Date Assignment Scheduling with Job-Dependent Learning Effects and Convex Resource Allocation. Engineering Optimization, 53, 1273-1281. https://doi.org/10.1080/0305215X.2020.1773813
[12]	Liu, W. and Jiang, C. (2020) Due-Date Assignment Scheduling Involving Job-Dependent Learning Effects and Convex Resource Allocation. Engineering Optimization, 52, 74-89. https://doi.org/10.1080/0305215X.2019.1580705