Synchronizing Schedules for Transportation
Site: | Saylor Academy |
Course: | BUS606: Operations and Supply Chain Management |
Book: | Synchronizing Schedules for Transportation |
Printed by: | Guest user |
Date: | Saturday, September 7, 2024, 7:40 PM |
Description
Read this article. It discusses synchronizing transportation schedules. Because the logistics segment of the cycle is a large-scale effort, the waiting and queues are magnified. How many different modes of transportation do you think are required to make a product from raw material to the customer's hand?
1. Introduction
Many companies are enhancing their competitiveness by offering Just-in-Time (JIT) delivery. Costs or penalties are incurred by delivering an order either earlier or later than the customer's due-dates. Besides, maintaining short response time from order acceptance to final delivery is one of the key competitive advantages. Thus, many companies deliver products to customers directly after production without holding finished product inventory. This is particularly true for the industries with short product life cycle, such as consumer electronics manufacturing, ready-mix concrete supplying, and food catering. In order to improve customer service and reduce production and transportation costs, scheduling of assembly manufacturing and transportation should be synchronized.
Nowadays, due to the professional services provided by third party logistics (3PL) provider, it is more efficient to outsource the transportation or distribution to 3PL. There are two types of operations. If 3PL only serves one customer, the schedule of 3PL's vehicle is determined by the order completion time in manufacturing. This type of operation is particularly true for 3PLs that providing road transportation services. On the hand, if 3PL provides services to more than one manufacturer, the departure and arrival time of the vehicle is determined by 3PL rather than by the manufacturer. In addition, the unit transportation cost of each vehicle varies. The manufacturer can book capacity on the available vehicles accordingly. Then, decision on allocation of orders to the vehicles is made to utilize the booked capacity efficiently. The typical case is the air-cargo transportation service provided by cargo airlines. Motivated by above application, this chapter studies the problem of synchronized scheduling of assembly manufacturing and transportation in the make-to-order (MTO) consumer electronics supply chain (CESC). In this context, materials or components are kept in inventory before assembly. Upon reception of customer orders, the materials are transferred to manufacturing job shop. Through several processes such as assembly, testing, packing, the assembly manufacturing is completed. Then, the order is transported to customers directly by the vehicle of 3PL. Chen and Vairaktarakis addressed the integrated production transportation scheduling problem considering the first type of 3PL operations, which is mentioned above. Conversely, the second type of 3PL operations is considered in this chapter.
The objective of this problem is first to determine appropriate allocation of orders to available vehicle capacities to minimize total delivery cost which consists of transportation cost, delivery earliness penalty cost, and delivery tardiness penalty cost. The allocation is constrained by production capacity. In other words, manufacturing of orders should be completed before the departure time of the vehicle that the order allocated to. Then, the schedule of assembly manufacturing is determined to make sure that each order is completed on time, while the order waiting time before transportation is minimized. According to Li et al., the solution method consists of two phases. A network representation of the two stage decision model is shown in Figure 1.
Figure 1. Two stage decision model in CESC
In the first phase, the proposed Integer Linear Programming (ILP) model will run for the transportation issues of the outbound logistics assuming that the number of completedcustomers'-orders are available and the production rate of assembly manufacturing is fixed and known. In the second phase, using the above optimal decision obtained for the outbound logistics, i.e., the flight wise customers' orders movement strategy, an efficient release control policy is decided for the assembly manufacturing based on the available assembly capacity.
The 3PL transportation allocation problem and the assembly scheduling problem formulated in this work are based on the following assumptions:
- Decisions of transportation allocation and assembly scheduling are for the orders accepted in the previous planning periods.
- All the packed products have same or similar dimensions.
- Business processing time and cost, together with loading time and loading cost for each vehicle are included in the transportation time and transportation cost.
- Vehicle departure time is taken as the time that 3PL's vehicle set out from the manufacturer's plant. Vehicle arrival time is taken as the time that the vehicle reaches customer.
- Orders released into production facility for the planning period are delivered within the same planning period which means there are no production backlogs.
- For assembly manufacturing, setup time is included in the processing time.
- Assembly flow shop consists of single machine. The machine can process only one part at a time.
- There are no machine breakdowns and preemptions.
- Total manufacturing time of an order is directly proportional to the order's quantity.
- Waiting penalties for orders before transportation are order independent, i.e., they are not determined based on any job characteristics.
- The starting time of the planning period is set equal to zero.
Source: Kunpeng Li and Appa Iyer Sivakumar, https://openresearchlibrary.org/content/a7cdb685-0a75-45dd-b097-f3c5e8f34f28
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.
2. The 3PL Transportation Problem
The 3PL transportation problem is formulated using an Integer Linear Programming (ILP) model. As the air transportation is a typical case for the 3PL transportation, the 3PL transportation is represented by air transportation hereafter. The model allocates orders to the existing air transportation capacities with minimum costs. Synchronization is incorporated into the ILP model by including the constraint that balances the production rate of the assembly facility with the flight allocation.
The following notation is defined:
i = order index, i=1, 2, …. N; f, f' = flight index, f=1,2,……F;
k = destination index, k = 1,2,……L; Af = arrival time of flight f at the destination;
Desi = order i's destination; Desf = flight f's destination;
LN = a large number; |LN| = absolute value of LN;
Qi = quantity of order i; di = due date of order i;
Df =departure time of flight f at the local place where the manufacturing plant is located;
NCf = transportation cost for per unit product allocated to normal capacity area of flight f; SCf = transportation cost for per unit product allocated to special capacity area of flight f;
NCapf = available normal capacity of flight f; SCapf = available special capacity of flight f;
Di = delivery earliness penalty cost (/unit/hour) of order i;
Ei = delivery tardiness penalty cost (/unit/hour) of order i;
WTi = waiting time of order i between assembly and air transportation;
PEif = per unit delivery earliness penalty cost for order i when it is transported by flight f,
PLif = per unit delivery tardiness penalty cost for order i when it is transported by flight f,
Zif = quantity of order i allocated to flight f
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;
PR = the production rate of assembly manufacturing;
In case of split deliveries, an order can be split and delivered among any number of flights. The ILP model for the multi-destination air transportation problem is expressed as follows:
Subject to:
The decision variables are: Xif, Yif, and Zif. All decision variables are non-negative integer variables. The objective is to minimize overall total cost which consists of total transportation cost for the orders allocated to the normal flight capacity, total transportation cost for orders allocated to the special flight capacity, total delivery earliness penalty cost, and total delivery tardiness penalty cost. Constraint (4) ensures that the quantity of the proportion of order i allocated into flight f consists of quantities of the proportion of order i allocated into normal capacity area of flight f and the proportion of order i allocated to special capacity area of flight f. Constraints (5) and (6) ensure that if order i and flight f have different destinations, order i cannot be allocated to flight f. Constraint (7) and (8) ensure that the normal and special capacity of flight f is not exceeded. Constraint (9) ensures that order i is completely allocated. Constraint (10) ensures that allocated orders do not exceed production capacity. It ensures that allocated quantity can be supplied by sufficient assembly capacity.
Subsequently, the equality of the above air transportation allocation problem with an unbalanced transportation problem is established. 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 points with different transportation costs. The unit transportation cost from a supply point SPi to a demand point DPf is the sum of the unit transportation cost and the unit delivery earliness (or tardiness) penalty cost of order SPi when transported by flight DPf . As total quantity of all orders is less than total capacity of all flights, the air transportation problem can be taken as an unbalanced transportation problem. As the transportation problem can be solved in polynomial time, this air transportation problem is also solvable using one of the commercial solvers.
3. Single Machine Assembly Scheduling Problem
For the assembly scheduling problem, the assembly flow shop is first assumed to be a single machine. A release time is determined for each order to minimize the average waiting time (AWT) before transportation. AWT is defined as the mean of sum of the waiting times for all orders. Transportation allocation results provide the inputs for the assembly problem which includes the orders, quantity, and transportation departure times. Orders may be split and allocated to different flights. The split orders will be treated as separate orders in assembly.
The transportation departure time is taken as the due date of assembly for each order. The assembly schedules adhere to the following conditions: (i) each machine processes only one job at a time (ii) pre-emption is not allowed, which means once a job’s processing is started, it can not interrupted by another job and (iii) processing time of each order is known. Two methodologies for assembly scheduling problem are presented in this section.
3.1 Forward Synchronized Scheduling Heuristic (FSSH)
Normally in practice, the schedules constructed use dispatching rules and follow a forward dispatch method. Forward approach schedules jobs in a given sequence one by one, starting from the first job, to achieve feasible and compact schedules. The approach usually generates non-delay schedules. A non-delay schedule is one in which no machine is kept idle at any time when at least one job is waiting for processing. Longest Processing Time (LPT) rule is selected as the dispatching rule. LPT minimizes total earliness in single machine scheduling in the situation of no tardiness for jobs. Since there may be split orders in allocation, the sequence determined by LPT rule may be adjusted to combine the split orders to facilitate assembly manufacturing while maintaining the transportation schedule of the split orders.
The general scheme for FSSH is:
Step 1: Group orders that are allocated to the same flight, and sequence the order groups by the rule of earliest flight departure time first.
Step 2: Use LPT rule to sequence the orders within the each group.
Step 3: Assembly batching of split orders (ABSO): This step is used to combine the split orders in a batch for assembly so that split orders in transportation can be treated as a whole order in assembly. This step is applied only in the situation when an order is split and allocated to two adjacent flights. The split orders are processed in sequence by scheduling them as last order for the first flight and first order for the second flight. This is to facilitate the assembly processing of an order.
Step 4: Calculate each order's release time by forward dispatch method starting from the first order to the last order. The first order's release time equals zero. The release time of succeeding orders are obtained by adding the assembly processing time of their preceding orders
Step 5: Compute the AWT between assembly and transportation.
The number of order groups in the planning period, corresponds to the number of flights that transport orders to the customer destinations, is determined by the transportation allocation model. Each order group consists of set of orders and they have same assembly due-date.
3.2 Backward Synchronized Scheduling Heuristic (BSSH)
Steps of BSSH are the same as FSSH except for step 4. Backward scheduling is used in step 4 in BSSH instead of forward scheduling in FSSH.
Backward scheduling is reverse of the forward scheduling approach and schedules are defined on a reverse time frame. The start time and completion time of the same job in forward scheduling mode is related to the completion time and start time of the same job in backward scheduling mode. In other words, the completion time of each job is determined first. The release time (or start time) for each job is then obtained using the determined completion time. To arrive at a schedule after using backward scheduling approach, the processing sequence is reversed, and the schedule time frame is reversed back to forward time frame.
The backward scheduling considers inserted idle times between processing of orders. Forward scheduling is a straightforward method that schedules jobs one by one from the beginning time of the planning period. The main objective is to make sure that each job can meet its due date. The forward scheduling methodology presented in the previous section does not minimize AWT effectively. This is overcome by adopting a backward approach that inserts idle times between order groups.
The last flight's departure time determines the completion time for the last order to be scheduled in the assembly in the planning period. To minimize order earliness before transportation, the favorable completion time for each order is their corresponding flight departure time. Hence, within each group, orders are scheduled one by one without inserted idle time in backward direction from the order group's due-date. Once the completion time for the last order to be scheduled in each group is determined, the release times for the preceding orders is calculated by subtracting its processing times from the release time of the succeeding orders. Idle times are inserted only between order groups. When the release time of the first order in the succeeding group is later than the current order group's due date, idle time is inserted between the two groups. Thus the last job of the current order group is scheduled to complete at the corresponding flight departure time.
The pseudo code description of the backward scheduling logic is presented below:
If (job i is the last job in flight j) then If (flight j is the last flight) then Release time(job i, flight j) =Departure time(flight j)– Processing time(job i, flight j) Else If (Release time (the first job, fight j+1) is earlier than Departure time(flight j)) then Release time (job i, flight j)=Release time (the first job, flight j+1) – Processing time(job i, flight j) Else Release time (job i, flight j) =Departure time (flight j) – Processing time (job i, flight j) End if End if Else Release time (job i, flight j) =Release time (job i+1, flight j) – Processing time (job i, flight j) End if
Computational results indicate that BSSH outperforms FSSH in terms of AWT. For detailed results of the comparison, it can be referred to Li et al.
4. Single Machine Assembly Scheduling Problem with random delay
Today's manufacturing environment is highly time varying, and most of the components in the supply chain have stochastic nature of objectives and constraints due to environmental uncertainties and executional uncertainties. These uncertainties can be triggered by machine breakdowns, shortage of materials, interruption of machine operations when their performance violates quality control standards, etc. The occurrence of interruptions and the time required for assembly to resume from the interruptions are often highly stochastic in nature. These issues always lead to unexpected delays in assembly. The deterministic schedule obtained prior to the start of assembly processing is affected and becomes inappropriate. Thus, the deterministic schedule should be updated so as to minimize the disturbances due to uncertainties. The scenario of assembly process delays caused by the stochastic events is studied and a schedule repair heuristic is presented to minimize the influence of stochastic events on deliveries.
There are two types of orders, viz., regular (non-delayed) orders and delayed orders. Regular (non-delayed) orders are the orders that are released into the shop as per the predetermined transportation allocation. Orders that have not been processed in assembly because of unexpected uncertainties are referred as delayed orders. The decision consists of the schedule of the delayed orders which have missed their earlier departure due-dates along with non-delayed orders. A delay is characterized by a start time and duration. It may result from machine breakdowns, shortage of materials, interruption of machine operations when their performance violates quality control standards, etc. The jobs completed prior to the delay are not taken into account. Hence, this section considers a situation of rescheduling the delayed orders along with non-delayed orders with a possibility of identifying a sequence in which non-delayed orders in the original schedule can reach their destination on time. It is also to be stated again that if an order misses it scheduled departure time it can only be shipped by a commercial fight at a higher cost. Basically, this possibility is considered to avoid a situation of very high disruptions caused in relation to the customer deliveries.
4.1 Problem formulation
The formulation presented in this section assumes that the new schedule Today's manufacturing environment is highly time varying, and most of the components in the supply chain have stochastic nature of objectives and constraints due to environmental uncertainties and executional uncertainties. These uncertainties can be triggered by machine breakdowns, shortage of materials, interruption of machine operations when their performance violates quality control standards, etc. The occurrence of interruptions and the time required for assembly to resume from the interruptions are often highly stochastic in nature. These issues always lead to unexpected delays in assembly. The deterministic schedule obtained prior to the start of assembly processing is affected and becomes inappropriate. Thus, the deterministic schedule should be updated so as to minimize the disturbances due to uncertainties. The scenario of assembly process delays caused by the stochastic events is studied and a schedule repair heuristic is presented to minimize the influence of stochastic events on deliveries.
the job/order index,
is the total number of jobs considered at the decision instant;
the assembly completion time of job
per unit transportation cost of job
when transported by a commercial flight;
the per hour earliness penalty of job
for assembly and it is assumed that
;
if job
precedes job
immediately, 0 otherwise;
if assembly completion time of job
is earlier than flight
's departure time, otherwise 0 ;
the predetermined allocation, 1 if job
is predetermined to be allocated to flight
by the ILP model, 0 otherwise;
the transportation cost matrix which is determined by the ILP model.
The model is expressed as follows:
Min
(11)
The
decision variables are Ri, PIij,
EFif. The objective function includes the two early and two late
penalties for the orders. Early
penalties are incurred when assembly of the order is completed earlier than its
transportation departure time. The late penalties are the special flight
transportation cost when orders miss their predetermined flight. Since the
assembly scheduling model considers synchronization with transportation, early
and late penalty for assembly together with final delivery early and late
penalties are taken into account in this model. The first term in the objective
function is the cost of early penalties of the orders when they can catch its
pre-determined flight. The early penalties consist of earliness cost before
transportation, predetermined flight transportation cost, final delivery
earliness/tardiness costs. The second term in the objective function is the
late penalties of the orders when they miss their predetermined flights. The
late penalties consist of the commercial flight transportation cost, the final
delivery earliness/tardiness costs.
Note that two dummy jobs are created in order to facilitate the representation of the immediate precedence of the jobs. They are the first and the last job which has zero quantity. Constraint (12) represents the relationship among the release time, completion time and processing time of each order. Constraint (13) sets the release time of the first job, R0, to the assembly resume time, which is the sum of delay start time t and the delay duration DU. Constraint (14) sets the release time of the last job, RN'+1, larger or equal to the total processing time of all the jobs. These two constraints denote that there might be inserted idle time between the release times of each two adjacent jobs. Constraint (15) and (17) ensure that all the jobs should have a precedence job except the first job. Constraint (16) and (18) ensures that all the jobs should have a successive job except the last job. Constraint (19) represents the completion time relationship between any two jobs. Constraint (20) and (21) indicate that when a job's completion time is earlier than a flight departure time, it can catch the flight. Constraint (22) indicates that PIij is 0-1 integer variable.
4.2 NP-completeness proof
To prove the assembly scheduling problem is NP-hard, it is reduced to a single machine scheduling problem with distinct due windows and job dependent earliness/tardiness penalty weights. The reduced problem is then proved to be NP-hard. Thus, the assembly scheduling problem investigated in this chapter is also NP-hard. In the following, the equivalence is established between the reduced problem and the problem studied by Wan & Yen, which is NP-hard.
The reduced problem: For the present discussion, the air transportation cost and time is ignored, as well as the final delivery earliness penalties. This is equivalent to say that these parameters take value zero. Therefore, the problem basically becomes a scheduling problem with distinct due-windows and job dependent earliness/tardiness penalty weights for each job. The due-window has a length equal to the difference between the final customer delivery time and transportation departure time.
Distinct due-windows: There is waiting cost if an order completed earlier than its assembly due date. As there is no earliness cost for final delivery, only tardiness cost is taken into account if the order is delivered later than the final due-date. Also, it is assumed that the air transportation cost and time are ignored. Therefore, the assembly of orders completed between assembly due-date and final due-date lead to no penalty. It is obvious that the number of flights corresponds to the number of due-dates for assembly. Thus, the assembly due-date is distinct. In addition, the final due-date of each order is distinct. Hence the reduced problem is a distinct due windows scheduling problem.
Job dependent earliness penalty: If assembly of a job is completed earlier than its due date, there is a waiting penalty, which depends on the product of the early time and the quantity of the job.
Job dependent tardiness penalty: As assumed that if an order is delivered later than its final due date, a late delivery penalty, which is the product of lateness time length and the order quantity, is incurred.
Wan & Yen show that the single machine scheduling problem with distinct due windows to minimize total weighted earliness and tardiness is NP-hard. As the reduced assembly scheduling problem is equivalent to the problem studied by Wan & Yen, the prior problem is NP-hard. Therefore, the assembly scheduling problem studied in this chapter is NP-hard.
4.3 Schedule Repair Heuristics
In many production situations, it is not desirable to reschedule all the non-delayed jobs along with the delayed jobs. Instead, the required changes should be performed in such a way that the entire system is affected as little as possible. This process is termed schedule repair in this chapter. To repair an unfinished schedule which has delayed orders, its valid parts (or the remaining unaffected schedule) should be re-used as far as possible, and only the parts touched by the disturbance are adjusted. At the beginning of assembly, the schedule obtained using BSSH is executed. Suppose the delay is caused by machine breakdown starting from time t and the assembly resumes after time length DU. Jobs that are to be released between t and t+DU in original schedule are only influenced by the disturbance. In line with the concept of schedule repair, the schedule after time t+DU is valid part and should be kept unchanged. The schedule of the influenced jobs between time t and t+DU should be adjusted.
The schedule generated using BSSH methodology will have idle times between job groups, during which the assembly does not work at its full capacity. The idle time can be utilized to process the delayed jobs. Therefore, a heuristic to repair the disturbed schedule is proposed is this section. The main motive is to insert the disturbed job into the idle time spans so that the assembly utilization is improved at the advantage of minimizing the delay penalties for the jobs. If still some jobs cannot be inserted into the idle time span, they are appended after the last job of the final schedule. Figure 2 illustrates this idea in detail.
Figure 2. Illustration of schedule repair heuristic
In Figure 2, the x axial denotes time. The blocks denote the scheduled jobs. During time t to t+DU, the jobs predetermined to be processed are denoted using shaded blocks. The delayed jobs are to be inserted into the idle times among the job groups in the BSSH schedule as denoted by the arc in the figure using the following heuristic.
The schedule repair heuristic (SRH):
1. Sequence the jobs scheduled between2. Insert disturbed jobs into the idle time spans between order groups. Suppose there are
2.2.
, insert job
into span
Else, go to
.
2.4. . If
, go to 2.7. Else, go to 2.2.
2.5. If
, go to
. Else, go to
.
2.6. Append the remaining jobs after the last job of the BSSH schedule.
2.7. Stop.
By computational experiments, it is shown that SRH can achieve good results. For detailed content, it can be referred to Li et al.
5. Conclusion and Further Research
In this chapter, the formulation of synchronized scheduling problem of production and transportation is presented. The solution methodology is to decompose the overall problem into two sub-problems, i.e., the transportation allocation problem and machine scheduling problem. The 3PL transportation allocation problem is formulated using an integer programming model. It is shown that the problem is solvable in polynomial time. Furthermore, the formulations for single machine with and without random delay are presented. The methods to solve these two problems are summarized. Further research can address the assembly sub-problem with parallel machines or sequential machines, etc.