Subscribe Now Subscribe Today
Research Article

Synchronized Production and Distribution Scheduling with Due Window

M. Zandieh and S. Molla- Alizadeh-Zavardehi
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

In this study, for coordination of production and distribution scheduling in the implementation of a supply chain solution, we studied the problem of synchronized scheduling of single machine and air transportation in supply chain management. The overall problem is decomposed into two sub-problems, which consists of air transportation allocation problem and a single machine scheduling problem which they are considered together. We have taken into consideration different constraints and assumptions in our modeling such as due window, delivery tardiness and no delivery tardiness. For these purposes, mathematical models have been proposed to minimize supply chain total cost which encompasses transportation, makespan, delivery earliness tardiness and departure time earliness tardiness costs.

Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

  How to cite this article:

M. Zandieh and S. Molla- Alizadeh-Zavardehi, 2008. Synchronized Production and Distribution Scheduling with Due Window. Journal of Applied Sciences, 8: 2752-2757.

DOI: 10.3923/jas.2008.2752.2757



A supply chain consists of all parties involved, directly or indirectly, in fulfilling a customer request. The supply chain includes suppliers, manufacturers, distributors, warehouses, retailers and even customers themselves. The key problem in a supply chain is a coordinated management and control of these activities.

Traditional scheduling problems assume that there are always infinitely many resources for delivering finished jobs to their destinations and no time is needed for their transportation, so that finished products can be transported to customer without delay. In accordance with this view there is a need for a synchronized procedure for generating more realistic production and distribution scheduling to be used in the supply chain. In this study, supply chain is shown in fig. 1. Within this chain, components are stored in inventory. On the receipt of an order from the customer, components and materials required for production are transferred to production line and then finished products are transferred to customers using air transportation to meet their due dates. Synchronization of production and air transportation is important, as the cost of missing a shipment in a scheduled flight is quite heavy and therefore, the missed shipment should be transported by special flights or commercial flights.

fig. 1: Supply chain stages synchronization

Therefore, in this study, the extra cost corresponding to commercial flights that we need to bear is called departure time tardiness. The departure time earliness costs could result from the need for storing the order at the production facility or waiting charges at the airport. Delivery penalties are incurred by delivering an order either earlier or later than the committed due date to customers. The delivery tardiness cost includes customer dissatisfaction, contract penalties, loss of sales and potential loss of reputation for manufacturer and retailers. If arrival time of allocated orders in air transportation model is earlier than its due date, retailers encounter delivery earliness. Therefore, delivery earliness cost considered as storing cost of orders by retailers.

We study the problem under two policies and they are as such: first policy considers delivery tardiness and the second one assumes that no delivery tardiness is authorized. The overall problem is decomposed into two coordinated tasks in each policy. The first task is to allocate accepted orders to available flights` capacities to minimize the total transportation cost and delivery earliness tardiness penalties according to the related situation and policy. The allocation is constrained by production such that allocation should be balanced with production capacity in the same situation and policy.

There seems to be little research on production scheduling considering air transportation. Li et al. (2004) studied the synchronization of single machine scheduling and air transportation with single destination. The overall problem is decomposed into air transportation problem and single machine scheduling problem. They formulated two problems and then presented a backward heuristic algorithm for single machine scheduling. Li et al. (2005) extended their previous work to consider multiple destinations in air transportation problem. Li et al. (2006a) showed the air transportation allocation have the structure of regular transportation problem, while the single machine scheduling problem is NP-hard. They also proposed a forward heuristic and a backward heuristic for single machine (Li et al., 2006b). Li et al. (2008) extended their work by considering parallel machines in production. The problem was formulated as a parallel machine with departure time earliness penalties. They also showed the parallel machine scheduling problem is NP-Complete and a simulated annealing based heuristic algorithm was presented to solve the parallel machine problem. They compared their simulated annealing algorithm with an operation method of a factory in Singapore (Li et al., 2007).

There also have been some discussions on synchronization of production and road transportation with emphasis on vehicle routing scheduling problem (Blumenfeld et al., 1991; Fumero and Vercellis, 1999; Chen, 2000; Lee and Chen, 2001; Chang and Lee, 2004; Chen and Vairaktarakis, 2005; Li et al., 2005; Soukhal et al., 2005; Li and Ou, 2005; Wang and Lee, 2005; Wang and Cheng, 2006; Zhong et al., 2007; Yuan et al., 2007; Chen and Lee, 2008). In addition, considerable research has been conducted in production-distribution integration. There are reviews on integrated analysis of production-distribution systems for more details see Vidal and Goetschalckx (1997), Erenguc et al. (1999), Sarmiento and Nagi (1999) and Goetschalckx et al. (2002).


The problem is formulated based on the following assumptions:

The plant treated as a single machine
Decisions of air transportation allocation and production scheduling are for the orders accepted in the previous planning period
There are multiple flights in the planning period with different transportation specifications such as cost, capacity, etc.
Business processing time and cost, together with loading time and loading cost for each flight are included in the transportation time and transportation cost
Local transportation transfers products from the plant to the airport. Local transportation time is assumed to be included in transportation time
Local transportation can transfer an order to the airport when the order is produced completely
Orders released into plant for the planning period are delivered within the same planning period, which means there are no production backlogs


The air transportation allocation problem: The air transportation model allocates orders to the existing transportation capacities that minimizes the total transportation cost and weighted delivery earliness tardiness penalties. We first corrected and illustrated the model proposed by Li et al. (2006) and then extended the model with considering due window and scheduling policies which are completely explained below. Synchronization is incorporated into the model by including the constraint that balances the production rate of the plant with the flight allocation.

The notations used here are defined as follows:

i,i`,j : The order or job index, i, i`, j = 1,2,...,N
f,f : The flight index, f, f` = 1,2,...,F
k : The destination index, k = 1,2,...,K
DF : The departure time of flight f at the local airport
Af : The arrival time of flight f at the destination
NCf : The transportation cost for per unit product when allocated to normal capacity area of flight f
SCf : The transportation cost for per unit product when allocated to special capacity area of flight f
Ncapf : The available normal capacity of flight f
Scapf : The available special capacity of flight f
Qi : The quantity of order i
αi : The delivery earliness penalty cost (/unit/h) of order i
βi : The delivery tardiness penalty cost (/unit/h) of order i
di : The due date of order i
Xif : The quantity of the portion of order i allocated to flight f`s normal capacity area
Yif : The quantity of the portion of order i allocated to flight f`s special capacity area
Desi : The order i`s destination
desf : The flight f`s destination
LN : A large positive number


: The processing time of order i
ei,li : The due window of order i, where ei is the earliest due date and li is the latest due date

Without loss of generality, it is assumed that D1≤D2≤...≤DF. The mathematical programming formulation of the model is shown as follow:


Subject to:








The objective is to minimize overall total cost which consists of total transportation cost for the orders allocated to normal flight capacity, total transportation cost for the orders allocated to special flight capacity, total delivery earliness tardiness penalties cost. Constraint sets 2 and 3 ensure that if order i and flight f have different destinations, order i cannot be allocated to flight f. Constraint sets 4 and 5 ensure that the normal and special capacity of flight f is not exceeded. Constraint set 6 ensures that order i is completely allocated. Constraint set 7 ensures that allocated orders do not exceed production capacity. It ensures that total orders related to allocated quantities can be produced by sufficient production capacity.

We can also use constraint set 9 or constraint sets 10 and 11 or constraint set 12 instead of constraint sets 2 and 3.





For the air transportation problem, each order can be taken as a supply point and each flight`s capacity can be taken as a demand point. It is noted that the normal capacity and special capacity of each flight are considered as two demand point with different transportation costs.

Due window: Typically the customers accept small deviation from delivery date, as they tolerate a small degree of uncertainty on the supplier`s side. This uncertainty might come about as a result of production problems such as defect in raw material, machine malfunctioning or problems with delivery itself such as flight`s delay, traffic jam, etc. It is generally agreed to accept small deviations from a delivery date and thus a delivery window (or due window) is arranged as shown in fig. 2 (Biskup and Feldmann, 2005).

The earliness time of order i is equal to max (0, ei-Af) and the tardiness time of order i is equal to max (0, Af-li). Hence the objective function is transformed as follows:


fig. 2: The penalty function around ei and li

The models with due window are generalized case of models with delivery date, because when both ei and li be equal to di the problem is transformed to models with delivery date.

An illustration: In order to validate and verify the proposed models, a common small problem is solved by the Lingo 8 software in all models. Consider a case of two orders (N = 2) with distinct destination 1 and 2 (Des1 = 1 and Des2 = 2) with quantities 30 and 40 (Q1 = 30 and Q2 = 40) such that each order can be transported by two flights with different departure times (F = 4, des1 = 2, des2 = 1, des3 = 1 and des4 = 2). The other parameters values for this example are as follows:

p1 = 4, p2 = 7, e1 = 12, l1 = 14, e2 = 15, l2 = 17, α1 = 4, α2 = 3, β1 = 7, β2 = 5, Des1 = 1, Des2 = 2, des1 = 2, des2 = 1, des3 = 1, des4 = 2, D1 = 8, D2 = 11, D3 = 16, D4 = 18, A1 = 9, A2 = 13, A3 = 17, A4 = 20, NCap1 = 20, NCap2 = 20, NCap3 = 20, NCap4 = 25, SCap1 = 20, SCap2 = 20, SCap3 = 10, SCap4 = 15, NC1 = 20, NC2 = 30, NC3 = 15, NC4 = 10, SC1 = 30, SC2 = 50, SC3 = 20, SC4 = 15.

The results obtained from solving this example are as follows:

X11 = 0, X12 = 20, X13 = 10, X14 = 0, X21 = 0, X22 = 0, X23 = 0, X24 = 25, Y11 = 0, Y12 = 0, Y13 = 0, Y14 = 0, Y21 = 0, Y22 = 0, Y23 = 0, Y24 = 15.

The production scheduling problem: The next task of the solution process is to determine the sequence and completion time for the allocated orders in production. This requires solving a production scheduling problem to ensure that allocated orders catch their flights so that total departure time earliness cost and plant cost is minimized. Transportation allocation results are the inputs for the production problem which include the order`s quantities allocated to flights. The required notation to present the model is as follows:

ci : The completion time of order or job i
α`i : The per hour earliness penalty of order or job i for production
p : The position or sequence of order i p = 1,2,...,N
uip : 1 if order i be in position p, 0 otherwise
λ : The per hour plant costs (including machine cost, operator wages and other production variable costs which is completely related to the length of working hours)
Ii :

The idle time before order i in the schedule

Cmax: : The maximum completion time of orders that is equal to shut down time of shop


Subject to:








The decision variables are ci, Ii, uip and Cmax. The objective function is to minimize the total weighted earliness penalties of jobs and plant cost. Constraint sets 15 and 16 state that each job has to be assigned to a position and each position has to be covered by a job. Constraint set 17 calculates completion time of jobs, considering inserted idle times among jobs. Constraint set 18 ensures that order i catches all of its departure times or the completion time of order is less than or equal to minimum of its related departure times. It means that all jobs must catch their all related scheduled flights. Constraint set 19 calculates Cmax and can be replaced by the constraint set 22.


The total cost of overall problem is the sum of objective function of air transportation and production scheduling models. Thus the total cost is as follows:


An illustration: The other required parameters are as follows:

The solutions are as follows:


The air transportation allocation problem: Since no tardiness is authorized, the objective function does not include the delivery tardiness costs and minimizes the total transportation costs and weighted delivery earliness penalties. Therefore, constraint set 25 ensures that the arrival time of all flights allocated to the order i is less than or equal to its delivery due date. The problem under study can be formulated as follows:


Subject to:


The other constraints of the model are the same as constraint sets 4-8 and 12.

Due window: The objective function 24 and constraint set 25 are changed as follows:


Subject to:


An illustration: The solutions are as follows:

X11 = 0, X12 = 20, X13 = 0, X14 = 0, X21 = 20, X22 = 0, X23 = 0, X24 = 0, Y11 = 0, Y12 = 10, Y13 = 0, Y14 = 0, Y21 = 20, Y22 = 0, Y23 = 0, Y24 = 0.

The production scheduling problem: Similar to the previous presented model for production scheduling the objective function is to minimize the weighted earliness penalties and plant cost and all jobs must catch their scheduled flights. So the objective function and constraints of the model are the same as that model. Total cost of the overall problem is the sum of objective function of two sub-problem of this section and is as follows:


An illustration: The solutions are as follows:


In this research, we studied supply chain synchronization problem. We have presented mathematical models with considering due window and scheduling policies. Numerical examples were performed to validate and verify the proposed models. Since there are a few researches about this subject, many researches can develop this paper. Further research can be conducted to consider other production configuration such as, parallel machine, flow shop, job shop, etc. Meta heuristics can also be applied to solve the proposed models. Future research can also be conducted by all assumption that studied in production scheduling and transportation scheduling research such as, set up time, ready time, stochastic processing time, non-split in transportation allocation, etc.

Biskup, D. and M. Feldmann, 2005. On scheduling around large restrictive common due windows. Eur. J. Operat. Res., 162: 740-761.
CrossRef  |  

Blumenfeld, D.E., L.D. Burns and C.F. Daganzo, 1991. Synchronizing production and transportation schedules. Transport. Res. B., 25: 23-27.
CrossRef  |  

Chang, Y.C. and C.Y. Lee, 2004. Machine scheduling with job delivery coordination. Eur. J. Operat. Res., 158: 470-487.
CrossRef  |  

Chen, B. and C.Y. Lee, 2008. Logistic scheduling with batching and transportation. Eur. J. Operat. Res., 189: 871-876.
CrossRef  |  

Chen, P., 2000. Integrating production and transportation scheduling in a make-to-order environment. Ph.D. Thesis. University of Cornell.

Chen, Z.L. and G.L. Vairaktarakis, 2005. Integrated scheduling of production and distribution operations. Manage. Sci., 51: 614-628.
CrossRef  |  

Erenguc, S.S., N.C. Simpson and A.J. Vakharia, 1999. Integrated scheduling of production/distribution planning in supply chain: An invited review. Eur. J. Operat. Res., 115: 219-236.
Direct Link  |  

Fumero, F. and C. Vercellis, 1999. Synchronized development of production, inventory and distribution schedules. Transport. Sci., 33: 330-340.
CrossRef  |  

Goetschalckx, M., C.J. Vidal and K. Dogan, 2002. Modeling and design of global logistics systems: A review of integrated strategic and tactical models and design algorithms. Eur. J. Oper. Res., 143: 1-18.
CrossRef  |  

Lee, C.Y. and Z.L. Chen, 2001. Machine scheduling with transportation considerations. J. Schedul., 4: 3-24.
CrossRef  |  

Li, C.L. and J. Ou, 2005. Machine scheduling with pickup and delivery. Nav. Res. Log., 52: 617-630.
CrossRef  |  

Li, C.L., G. Vairaktarakis and C.Y. Lee, 2005. Machine scheduling with deliveries to multiple customer locations. Eur. J. Operat. Res., 164: 39-51.
CrossRef  |  

Li, K.P., A.I. Sivakumar and V.K. Ganesan, 2008. Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronic supply chain. Eur. J. Operat. Res., 187: 442-455.
Direct Link  |  

Li, K.P., A.I. Sivakumar, M. Mathirajan and V.K. Ganesan, 2004. Solution methodology for synchronizing assembly manufacturing and air transportation of consumer electronics supply chain. Int. J. Business, 9: 361-380.
Direct Link  |  

Li, K.P., A.I. Sivakumar, Q. Fu and X. Jin, 2007. A case study for synchronized scheduling and manufacturing and air transportation in consumer electronics supply chain. Proceedings of the Conference on Industrial Engineering and Engineering Management (IEEM), December 2-4, 2007, Singapore, pp: 1629-1633.

Li, K.P., V.K. Ganesan and A.I. Sivakumar, 2005. Synchronized scheduling of assembly and multi-destination air transportation in a consumer electronics supply chain. Int. J. Prod. Res., 43: 2671-2685.
CrossRef  |  

Li, K.P., V.K. Ganesan and A.I. Sivakumar, 2006. Scheduling of single stage assembly with air transportation in a consumer electronic supply chain. Comput. Ind. Eng., 51: 264-278.
CrossRef  |  

Li, K.P., V.K. Ganesan and A.I. Sivakumar, 2006. Methodologies for synchronized scheduling of assembly and air transportation in a consumer electronic supply chain. Int. J. Log. Syst. Manage., 2: 52-67.

Sarmiento, A.M. and R. Nagi, 1999. A review of integrated analysis of production-distribution systems. IIE Trans., 31: 1061-1074.
Direct Link  |  

Soukhal, A., A. Oulmara and P. Martineau, 2005. Complexity of flow shop scheduling problems with transportation constraints. Eur. J. Operat. Res., 161: 32-41.
CrossRef  |  

Vidal, C. and M. Goetschalckx, 1997. Strategic production-distribution models: A critical review with emphasis on global supply chain models. Eur. J. Operat. Res., 98: 1-18.
CrossRef  |  

Wang, H. and C.Y. Lee, 2005. Production and transport logistics scheduling with two transport mode choices. Nav. Res. Log., 52: 796-809.
CrossRef  |  

Wang, X. and T.C.E. Cheng, 2007. Machine scheduling with an availability constraint and job delivery coordination. Nav. Res. Log., 54: 11-20.
CrossRef  |  

Yang, J., A. Soukhal, Y. Chen and L. Lu, 2007. A note on the complexity of flow shop scheduling with transportation constraints. Eur. J. Operat. Res., 178: 918-925.
CrossRef  |  

Zhong, W., G. Dosa and Z. Tan, 2007. On the machine scheduling problem with job delivery coordination. Eur. J. Operat. Res., 182: 1057-1072.
CrossRef  |  

©  2020 Science Alert. All Rights Reserved