|
Article Excerpt
We study the upstream supplier's batch scheduling problem in a supply chain, which was defined by Hall and Potts [Hall, N. G., C. N. Potts. 2003. Supply chain scheduling: Batching and delivery. Oper. Res. 51(4) 566-584]. The supplier has to manufacture multiple products and deliver them to customers in batches. There is an associated delivery cost with each batch. The objective of the supplier is to minimize the total inventory holding and delivery costs. We present simple approximation algorithms for this strongly NP-hard problem, which find a solution that is guaranteed to have a cost at most 3/2 times the minimum. We also prove that the approximation algorithms have worst-case bounds that vary parametrically with the data and that for realistic parameter values are much better than 3/2. The theoretical results are also supported by the findings of a computational study.
Subject classifications: production/scheduling; sequencing; deterministic; single machine; manufacturing; performance/productivity.
Area of review: Manufacturing, Service, and Supply Chain Operations.
History: Received May 2005; revisions received June 2006, November 2007; accepted January 2008. Published online in Articles in Advance February 26, 2009.
1. Introduction
Supply chain management has been one of the most important topics in manufacturing research over the past 15 years. Whereas most of the supply chain literature focuses on inventory control issues on the strategic level, using stochastic models, Thomas and Griffin (1996) point out in their review of the literature that for many products logistics expenditures can constitute as much as 30% of their cost. This underlines the need for research dealing with supply chain problems on the operational level, using deterministic rather than stochastic models. The recently emerging research area of supply chain scheduling tries to address this problem.
Because it is a new area for research, there are relatively few papers dealing specifically with scheduling problems in supply chains. Hall and Potts (2003) presented the first paper on this important topic. They study a variety of scheduling, batching, and delivery problems in supply chains with the objective of minimizing the overall scheduling and delivery cost. Chen and Hall (2007) and Dawande et al. (2006) extend these to supply chains with assembly-type manufacturing systems and distribution systems, respectively. Agnetis et al. (2006) study issues of sequence coordination between the different decision makers. Some of the problems in these papers are related to previous work on coordinating production and distribution systems. Williams (1983) and Lee and Chen (2001) consider the integration of transportation time and capacity issues with scheduling decisions. Li et al. (2005) study the problem of minimizing the average job-arrival times, which include travel times to the customers. Chen and Vairaktarakis (2005) present polynomial-time solutions (with a fixed number of customers) for the problem of minimizing a convex combination of the mean arrival times and the total distribution cost, where the latter includes fixed delivery costs and variable costs dependent on the delivery routes. The related problem we study in this paper considers the weighted sum of delivery times (for the inventory holding costs) but includes only the fixed part of the delivery costs with no routing decisions.
Depending on the number of stages in the supply chain, operating it may involve decisions by several decision makers, e.g., the supplier and the customers. This gives rise to a rich variety of optimization problems for each decision maker and possibly issues of coordination between them. One of the most important and fundamental supply chain scheduling problems studied by Hall and Potts (2003) is the supplier's problem of minimizing the sum of inventory holding costs and delivery costs in a supply chain, where large quantities of different products are processed and delivered in batches to customers. The supplier's operating environment is modeled as a one-stage system (machine). The problem is closely related to batch scheduling problems, on which there is a substantial body of literature. We briefly review these next.
Potts and Van Wassenhove (1992), Albers and Brucker (1993), Webster and Baker (1995), and Potts and Kovalyov (2000) give comprehensive surveys on batch scheduling. Several papers deal with one-machine batch scheduling problems in which the objective is to minimize the inventory holding cost. Dobson et al. (1987), Santos and Magazine (1985), Naddef and Santos (1988), and Coffman et al. (1990) study the batching of identical items processed on a single machine to minimize the inventory holding cost when each batch requires a setup. They give explicit formulas for determining the optimal number of batches to be used, which leads to pseudopolynomial solutions for the problem. Shallcross (1992) presents a polynomialtime solution. Dobson et al. (1987) and Naddef and Santos (1988) also propose heuristic solutions for the corresponding N-product problem under the assumption that only copies of the same product can be batched together. Monma and Potts (1989) study the batching problem in a one-machine environment for N products, where a batch may contain items from different products. They prove that jobs within each batch are sequenced in weighted-shortest-processing-time (WSPT) order in the optimal batching to minimize the inventory holding cost. Some batch scheduling papers also include delivery cost or delivery time considerations. Among these, Cheng et al. (1996) study the batch scheduling problem on a single machine to minimize the sum of delivery costs and earliness penalties. Hermann and Lee (1993) and Chen (1997) consider models with the objective of minimizing earliness/tardiness penalties and batch delivery costs. Hall and Potts (2005) study the coordination of scheduling and batch deliveries with various scheduling objectives. Yang (2000) analyzes a model with given batch delivery dates, and Hall et al. (2001) study similar problems in different machine environments. Chen (1996) presents a dynamic programming algorithm for single-machine scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs.
In this paper, we study the supplier's problem introduced by Hall and Potts (2003), i.e., the problem of scheduling multiple products in batches at an upstream supplier to minimize inventory holding costs and delivery costs in the supply chain, where the supplier's entire system can be viewed as a single "machine." The supplier has m customers, [M.sub.1], [M.sub.2],..., [M.sub.m]. Because of the scheduling context, we will often refer to products as jobs and also call the inventory holding cost per unit of time the weight of the job. There are [N.sub.k] jobs, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], to be processed for customer [M.sub.k] on a single machine. Job [J.sub.i.sup.(k)] has processing time [p.sub.i.sup.(k)] and weight [w.sub.i.sup.(k)] for i = 1, 2,..., [N.sub.k] and k = 1, 2,..., m. Thus, the total number of jobs to be scheduled is N = [[SIGMA].sub.[k = 1].sup.m] [N.sub.k]. Jobs for the same customer are to be delivered in batches. We make no assumption about the type of delivery method used, other than it is not constraining the feasibility of delivery schedules. So, for example, if trucks were used, we assume that their capacity is nonrestrictive (infinite) and that there is always a sufficient number of them available to deliver the batches at their scheduled time. Associated with each batch is a fixed batch delivery cost d. We note that we make this assumption only for reasons of notational convenience, and all of our results remain valid even if the delivery costs vary by customer. All of the jobs are available at time t = 0, and a job is considered to be in inventory until the last job in its batch is finished, at which time the batch gets delivered. This is usually referred to as the batch availability assumption. We have to find the job sequence [sigma], the number of batches n, and the job assignments to batches so that the sum of the inventory holding costs (weighted flow or completion times) and batch delivery costs is minimized. Therefore, we will also refer to this problem as the batch delivery scheduling problem. Let us number the batches by i = 1, 2,..., n...
|
