برنامه ریزی زنجیره تامین و هماهنگی با حالت های تحویل دوگانه و هزینه ذخیره سازی موجودی

We study a two-echelon supply chain scheduling problem in which a manufacturer acquires supplies from an upstream supplier and processes orders from the downstream retailers. The supply chain sells a single short-life product in a single season. We consider the scenario where the manufacturer can only accept some of the orders from the retailers due to its supplier's common production time window and its own two common production and delivery time windows. The upstream supplier processes materials and delivers the semi-finished products to the manufacturer within its time window. Then the manufacturer further processes these products to produce finished products and delivers them to the retailers within its two time windows, where one window is for production and normal delivery, and the other is for production and express delivery. Having to store the materials before processing them, the supplier incurs a storage cost, which depends on the order size and storage time. The manufacturer pays the transportation cost for delivering the finished products to the retailers. Due to double marginalization, the performance of the supply chain is sub-optimal. We model the supply chain problem as a flow shop scheduling problem with multiple common time windows. We derive some dominance properties and establish some theorems that help solve the sequencing problems for the orders and eliminate the idle time among the orders. Based on these results, we develop fast pseudo-polynomial dynamic algorithms to optimally solve the problem. We prove that the problem is NP-hard in the ordinary sense only. We develop two practically relevant and robust methods for the supply chain to achieve optimal profit-making performance through channel coordination.

Scheduling problems in the two-echelon supply chain are challenging due to their combinatorial nature. The reason is that as the number of possible schedules for the problems is huge, the time required to solve the problems is prohibitively long (Blazewicz et al., 2001). Hence it is important to develop fast algorithms to produce solutions under reasonably restricted conditions. In a decentralized supply chain, individual parties have their own profit structures. Thus they make decisions that maximize their own profits and this will usually lead to a sub-optimal supply chain. In this paper we consider a supply chain that has an upstream supplier (M1) and a downstream manufacturer (M2), where M2 accepts some of the n orders Ji (i=1,2, …, n) from n retailers. Specifically, in our problem, we consider a supply chain that sells a short-life product in a single season, where the product requires a long production lead-time. Hence each retailer only places a single order with M2 and it has no re-ordering opportunity. To process an order Ji with time pi,2 from a retailer, M2 needs to first acquire semi-finished products from M1, which has processed the materials with time pi,1, i=1,2, …, n. Then M2 further processes the semi-finished products to produce the finished products. All the orders are available at time 0 and they share a common selling season. We assume that both M1 and M2 adopt the make-to-order strategy. Due to production capacity limits in the supply chain, e.g., production manpower and machines are limited, each of M1 and M2 can only process one order at a time, and M2 cannot accept all of the retailers' orders. The retailers specify the due date of receiving the finished products such that the latest common delivery start time for the manufacturer's normal delivery is d2. The express delivery is used when the normal delivery cannot meet the receiving due date, where the express delivery time window is given by (d2,d3] such that the latest common delivery start time for the manufacturer's express delivery is d3. Note that the receiving due date is later than d2 and d3. We consider that M2 starts to deliver the finished products no later than d2 in the normal delivery mode and starts to deliver the products within (d2,d3] in the express delivery mode because any delay will cause a substantial loss of profit to the retailers and M2 will suffer from a substantial loss of goodwill. In addition, M1 must (i) finish processing the materials no later than d1 and then (ii) immediately deliver the semi-finished products to M2 after processing the materials, where the given parameter d1 is less than the parameter d2. Also, M1 needs to store the materials before processing them, and the storage cost depends on the sizes of the orders and the time of storing the materials. The size of an order qi is agreeable with its processing time pi,1 on M1, i=1,2, …, n (i.e., q1≤q2≤⋯≤qn implies p1,1≤p2,1≤⋯≤pn,1). Thus the storage cost for storing the materials before processing on M1 is measured by θqisi,1, where θ and si,1 are the storage cost per unit quantity per unit time and the start time of processing order Ji,1 on M1, i=1,2, …, n, respectively (the storage time is the time duration between time 0 and si,1). Moreover, we consider the scenario where the production lead (processing) times have been reduced to the minimum so they are the given parameters (not decision variables). Thus we focus on minimizing the transportation cost rather than the production lead times. Regarding the transportation cost, we assume that the distance between M1 and M2 is short so the transportation lead time between M1 and M2 and the associated transportation cost is negligible. However, the distance between M2 and retailer i is long, so a substantial transportation cost is incurred. This transportation cost of order Ji is qiαi, which depends on the size of the order (quantity) qi and the mode of delivery between M2 and retailer i, where the normal transportation cost per unit quantity is αi and the express transportation cost per unit quantity is βi, i=1,2, …, n. We assume that all the retailers are located in the same geographical zone as far as the transportation cost is concerned. Hence the distances between the manufacturer and the retailers need not be expressed explicitly in our problem because the same zone-to-zone distance is already incorporated into αi and βi for i=1,2, …, n. In order to maximize the profit by accepting more orders, M2 uses the express delivery mode of transport to deliver the finished products, which is charged at a higher unit transportation cost, so βi>αi, i=1,2, …, n. The problem is motivated by a supply chain problem commonly found in apparel production, where M2 is a garment factory (in a developing country such as China) that produces apparel products and M1 is a textile company (which is located closely to M2) that supplies the fabrics for M2. The retail buyers, such as those from national fashion brands, are usually located in the developed countries in North America and Europe. The issue of transportation cost (and time) as described above hence arises. In order to fulfill the retail buyers' orders, e.g., a certain quantity of polo shirts, M2 needs to perform production operations such as cutting, assembly, quality checking, etc, whereas M1 needs to perform the operation of dyeing (e.g., from gray yarn). In this setting, the production (processing) time of an order at M2 (called an M2-order) is usually longer than that of the order at M1 (called an M1-order) because for M1 dyeing is rather straightforward and the required time increases with the quantity of gray yarn. Obviously, for M2, the production time also increases with the ordered quantity of polo shirts. As a consequence, the production times of M1 and M2 are agreeable because a larger order requires a longer production time, i.e., mathematically the processing times of orders Ji and Jk satisfy the following condition: if pi,1<pk,1, then pi,2<pk,2, for i,k=1,2, …, n (i≠k), where pi,1<pi,2 for all i=1,2, …, n (since making garment to fulfill an M2-order takes a longer time than dyeing the fabrics for the corresponding M1-order). We note that the processing time of an M1-order can be longer than that of another M2-order due to the larger size of that specific M1-order, so idle time may be incurred on M2. In addition, for many garment factories, in order to meet the due date requirements specified by the retailers, they could consider using the express delivery. Despite being relatively costly, this has become a common industrial practice, given the importance of meeting customer (retailers') due dates and the relatively lower transportation costs of express delivery when manufacturers form strategic alliances with logistics companies and garment factories. With the industrial motivation and the problem setting presented above, we formulate the above problem as a two-machine multiple common time windows flow shop scheduling problem, in which the first machine is M1 and the second machine is M2. We first analytically explore the decentralized case where M2 is the decision maker, which determines the optimal order set and the optimal schedule of the orders to process so that its profit is maximized. We then study the centralized case, in which a supply chain coordinator (M2 or M1) exists that strives to find the best schedule for the whole supply chain. We prove that all the decentralized and centralized cases are NP-hard in the ordinary sense only. The two-machine flow shop scheduling problem has been widely studied in the literature. For example, Jozefowska et al. (1994) consider the problem to minimize the weighted number of tardy jobs with a common due date. They prove that the problem is NP-hard in the ordinary sense. Della Croce et al. (2000) investigate the problem to minimize tardiness with equal weights. They devise a branch-and-bound algorithm to find an optimal solution for the problem. Yeung et al. (2004) consider the problem to minimize earliness and tardiness with a common due window. They show that the problem is strongly NP-hard, and develop a branch-and-bound algorithm and a heuristic algorithm to solve the problem. Most recently, Yeung et al. (2010) studied the optimal scheduling of a single-supplier single-manufacturer supply chain with common due windows. They show that the problem is NP-hard and develop a pseudo-polynomial algorithm to optimally solve the problem. They develop a method that eliminates the need for generating all the optimal partial schedules to obtain an optimal solution, thus reducing the running time for solving the problem. For a survey on research and some updates related to flow shop scheduling problems, we refer the reader to Gupta and Stafford (2006) and Qi (2011). All these works provide us with the foundation to study related scheduling problems in supply chain management. Unlike the problems in the literature, our model incorporates the transportation issue involving two delivery time windows and dual transport delivery modes. The model is challenging because it requires a fast algorithm to solve the problem in real life. This may be the reason why there is a lack of optimal solution algorithms for the problem in the literature. In addition, fast optimal algorithms are required to maximize the efficiency of channel coordination in the supply chain without a closed-form solution. The solution algorithms developed in this paper fill this gap. In the context of multi-echelon supply chain management, many channel coordination schemes have been proposed in the literature to deal with challenges such as double marginalization.1 Some coordination methods are also motivated by the industrial cases with short-life fashionable products (e.g., Chen and Xu, 2001, Liu et al., 2006 and Wei and Choi, 2010). Methods for coordinating inventory decisions in a multi-echelon supply chain include the returns policy, sales rebates (Chiu et al., 2011), quantity discounts scheme (Xiao et al., 2007), price-subsidy policy (Xiao et al., 2005), etc. We refer the reader to Tsay et al. (1999) and Cachon (2003) for details of these methods. As for research on supply chain scheduling problems, Cheng and Kovalyov (2001) consider the problem of scheduling the production and delivery of a supplier to feed the production of manufacturers. The problem is to minimize the total setup cost of switching from processing one order to another order placed by the manufacturers. They prove that the problem is NP-hard in the ordinary sense. Hall and Potts (2003) study several batching and delivery scheduling problems and prove that the problems are NP-hard in the strong sense. With the assumption that the sequences of the orders within groups to be processed on the machines are given, they develop pseudo-polynomial dynamic programming algorithms for the problems. They also illustrate with some examples that substantial benefits can result from coordination between the supplier and the manufacturer. Li and Xiao (2004) study the supply chain coordination problem with lot streaming, where the machines in a multiple-stage production process are managed by different supply chain members. They develop and analyze coordination mechanisms that enable different supply chain members to coordinate their lot splitting decisions in order to achieve a system-wide optimum. Recently, Xiao et al., 2005 and Xiao et al., 2007 and Chiu et al. (2011) studied supply chain coordination schemes in different settings. Xiao et al. (2005) establish a price-subsidy contract and demonstrate that it can successfully coordinate a supply chain with one manufacturer and multiple retailers. Xiao et al. (2007) study supply chain coordination mechanisms under either a linear quantity discount schedule or an all-unit quantity discount scenario. They derive the mechanisms for achieving supply chain coordination under each scenario and provide managerial insights. Chiu et al. (2011) study the supply chain coordination problem with price dependent demands. By employing a flexible combined contract with wholesale price, rebate, and returns, they successfully coordinate the supply chain with both the additive and multiplicative demands. Other related works on supply chain coordination include Choi (2006), Leng and Parlar (2009), Li et al. (2009), Sawik (2009), Chen et al. (2010), Kang and Kim (2010), Bhatnagar et al. (2011), and Yang et al. (in press). In this paper we study supply chain scheduling and channel coordination via the two-machine flow shop scheduling model. The rest of this paper is organized as follows: we formulate the analytical models for the decentralized and centralized cases of the general problem in Section 2. In Section 3 we identify dominance properties that help reduce the computational time for optimally solving the cases (problems). In Section 4 we present the solution algorithms for the problems and show that the problems are NP-hard in the ordinary sense only. In Section 5 we report the results of computational experiments conducted to test the efficiency of our algorithms. We develop two methods to achieve channel coordination in the supply chain in Section 6. We conclude the paper in Section 7.

We study a two-echelon supply chain scheduling problem in which there is a supplier, and a manufacturer who receives orders from the retailers and then orders supplies from the supplier to produce the products. The manufacturer can accept only some of the orders because of production and delivery time constraints in the supply chain. The objective of the problem is to maximize the profit, subject to sizes of the orders, time-dependent storage costs, and transportation costs of dual delivery modes in the supply chain. We formulate the problem as a two-machine multiple common time windows flow shop scheduling problem. Unlike the problems in the literature, our model incorporates the transportation issue involving several time windows and dual transport delivery modes. The model is challenging because it requires a fast algorithm to solve real-life problems. We consider both the centralized and decentralized cases. We derive dominance properties and establish theorems to deal with the issues of order sequencing and eliminating machine idle time, which helps optimally solve the problems. We develop fast pseudo-polynomial dynamic programming algorithms for the problems. We show that the problems are NP-hard in the ordinary sense only. We also show that there exists an optimal sequence for all the problems, where the orders of the supplier follows the shortest processing time (SPT) rule and the orders of the manufacturer follow the same sequence of the supplier. We identify the conditions under which win–win channel coordination can be achieved. We present two methods to achieve optimal supply chain profit-making performance through channel coordination under a contract that requires fast and optimal solutions for implementation. Future research can be undertaken by extending our model to consider resource-dependent processing times (e.g., Shabtay et al., 2007), by incorporating sequence-dependent setup times (costs) (for a literature review on this topic, please see Zhu and Wilhelm, 2006), or by studying a more complex supply chain structure in a stochastic environment. For instance, Elmaghraby and Thoney's (1999) results for the two-machine stochastic flow shop problem to minimize the expected makespan and our results in this paper can be used as a foundation for such an extension. Moreover, it will be interesting to explore the stochastic case with risk averse supply chain agents (see Choi et al., 2008, Xiao and Choi, 2009, Choi and Chiu, in press and Choi et al., in press for some probable models). Last but not the least, it will also be interesting to explore the feasibility of extending the model for tackling challenging and realistic industrial production problems such as mass customization scheduling (see Yao and Liu, 2009 and Yeung and Choi, 2011 for more details of the related issues).