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

In a supply chain, a manufacturer receives jobs from suppliers at distinct time points, and produces and delivers final products to customers in batches. The manufacturer can be modeled as a single machine in the supply chain and the problem can thus be modelled as minimizing the sum of weighted flow time and the batch delivery costs. Since the problem with arbitrary processing times, release times and weights is strongly NP-hardNP-hard, we first analyze some polynomially solvable special problems. Then we develop a heuristic algorithm to solve the general problem. We also develop a lower bound to study the performance of our heuristic algorithm and the computational experiments show that the solutions of the heuristic algorithm are close to optimal solution.

Supply chain management has been one of the most important topics in manufacturing research. Scheduling models which consider inbound productions and outbound deliveries simultaneously can improve the overall performance of supply chains. The recently emerging research area of supply chain scheduling tries to address this problem. Hall and Potts (2003) study several supply chain scheduling problems by including delivery costs in addition to the scheduling costs in the objective. (Readers may refer to Chen and Hall, 2007, Dawande et al., 2006, Agnetis et al., 2006, Chen and Lee, 2008, Shabtay, 2010, Wang and Cheng, 2000, Hall et al., 2008 and Pundoor and Chen, 2009). All these papers, consider the objective of minimizing the sum of weighted flow times (or sum of flow times), where weighted flow time can be interpreted as inventory holding costs. If we consider an individual production system (or organization) as a single machine, and times at which orders (or raw materials) arrive the system as release times, then the problem will be equivalent to batch scheduling on a single machine with release times. A job can be delivered to the customer if its processing is completed. In most cases, there incur delivery costs when delivering completed jobs to customers. Therefore, jobs are delivered in batches to customers to save delivery costs. However, the waiting of jobs in the system for delivery increases the holding cost. Therefore, we need to find a trade-off between increase in inventory holding cost and decrease in delivery cost. Selvarajah and Steiner (2009) study this problem at the supplier with multiple customers, where all jobs are available for processing at time zero. They present a 1.5-approximation algorithm, and perform a parametric analysis on the data to prove that the algorithm yields solutions closer to the optimal solutions for problems where data fall into realistic ranges. Halim and Ohta (1994) study batch scheduling to minimize sum of flow time at manufacturers when job arrivals and final product deliveries are to follow just-in-time philosophy. In this paper, we study batch scheduling at the manufacturer, where jobs are received at distinct time points from suppliers, and there incurs a delivery cost each time a delivery is made to a customer. Thus, our problem is defined as follows: We are given a job set J={S1,S2,…,Sm}J={S1,S2,…,Sm} for m customers, where Si={Ji,1,Ji,2,…,Ji,ni}Si={Ji,1,Ji,2,…,Ji,ni} is the job set for customer View the MathML sourceIi,i=1,2,…,m, and the number of jobs is View the MathML sourcen=∑i=1mni. In most real cases, m is relatively stable for a manufacturer. This justifies our assumption that the number of customers, m is fixed . Ji,kJi,k represents the k -th job of customer I i. For each job Ji,kJi,k, denoted by pi,kpi,k, ri,kri,k, and wi,kwi,k, respectively are the processing time , release time and weight . Only the jobs belonging to the same customer can be delivered in the same batch. Associated with each batch is a delivery cost q i, for customer I i, i≤mi≤m. Our goal is to find a schedule which minimizes the sum of the holding and the delivery costs. In scheduling literature, the unit holding cost of job Ji,kJi,k is called the weight wi,kwi,k and the time period during which Ji,kJi,k is in the system is called the flow time Fi,kFi,k. Therefore, the cost of holding Ji,kJi,k in the system is (wi,k×Fi,k)(wi,k×Fi,k). Let Ci,kCi,k be the completion time of Ji,kJi,k. Then we know that the delivery time Di,kDi,k of job Ji,kJi,k is greater or equal to Ci,kCi,k and Fi,k=Di,k−ri,kFi,k=Di,k−ri,k. Extending the three-field notation ( Graham et al., 1979), the problem can be denoted by 1|m,ri,k|∑wi,kFi,k+∑biqi1|m,ri,k|∑wi,kFi,k+∑biqi, where bi is the number of batches for customer Ii in a schedule. We also make the following assumptions: (1) once a job gets started, no interruption is allowed during its processing; (2) all the data is nonnegative integers; (3) all data is well-defined before time zero; (4) delivery costs are independent of batch sizes. Lenstra et al. (1977) prove that sequencing of jobs with arbitrary release times on a single machine to minimize sum of completion time is strongly NP-hardNP-hard. Further, Labetoulle et al. (1984) prove that sequencing of jobs with arbitrary release times on a single machine to minimize sum of weighted completion time is strongly NP-hardNP-hard even when preemption is allowed. Therefore, it is clear that our batch scheduling problem is strongly NP-hardNP-hard even when preemption is allowed. Hall and Potts (2003) study similar problem with the assumption that jobs of the same customer follow a fixed job sequence. They interpret release times as arrival times of orders delivered by suppliers and present a dynamic programming algorithm with time complexity O(n3m)O(n3m) for the problem where jobs have identical weights. In fact, their dynamic programming algorithm for given job sequence can easily be modified for the problem when jobs have arbitrary weights. We first study few special cases of the problem that can be solved polynomially. Then for the general problem, we develop heuristic algorithm and develop a lower bound to test the performance of the algorithm.

In this paper, we studied supply chain scheduling problem at the manufacturer to minimize the sum of holding and delivery costs, 1|m,ri,k|∑wi,kFi,k+∑biqi1|m,ri,k|∑wi,kFi,k+∑biqi. Since the problem is strongly NP-hardNP-hard even for the preemptive problem with zero delivery cost, we first analyzed some special problems that are polynomially solvable and presented polynomial algorithms for those problems. Also we have briefly discussed these algorithms can be simply modified to solve problem with any objective functions which are monotone non-decreasing function of completion times. For the general case, we presented a hierarchical heuristic algorithm which uses RKGA for job sequencing and the polynomial algorithm, which we developed for fixed-all-job-sequence in Section 3, for the optimal batching. We tested our heuristic algorithm with a lower bound algorithm and computational experiments show that the average gap is less than 10% when the batch delivery costs are in the interval (500,1000) units, and (1000,2000) except for one instance. The increase in the gap, when the delivery costs are set in the interval (1500,3000), can be explained due to batching of jobs across customers, and selecting the minimum delivery cost. However, the performance of the algorithm is very good compared to the lower bound even though the lower bound is very loose. Work on finding a tighter lower bound is one possible future research. Also experimenting on other heuristics to compare algorithm performance and developing approximation algorithms can be some potential works. For the manufacturer's problems, Hall and Potts (2003) did exclusive studies on all scheduling measures plus delivery costs with the fixed-customer-job-sequence assumption. In Section 3, we assumed that all the jobs have a fixed sequence according to their release times. This fixed-all-job-sequence assumption is common in practice such as processing jobs in FIFO (first in first out). Under this assumption, we studied the holding costs (total weighted completion times) together with delivery costs on a single machine.