Integration of Job Scheduling with Delivery Vehicles Routing

INTRODUCTION

One of the most important things in implementing supply chain management is to efficiently control the physical flow of the supply chain (Lee et al., 2006). A supply chain is a network of interlinked suppliers, manufacturers, distributors and customers. Supply chain management represents a new focus on how to link organizational units to best serve customer needs and to improve the competitiveness of a supply chain (Stadtler, 2005). The coordination of activities along different stages of a supply chain has received much attention in operations and logistics management research. The tendency has created closer interactions between the stages in a supply chain increasing the usefulness of integrated models. In such an integrated system, the linkage between job scheduling (the production stage) and finished goods delivery (the distribution stage) is very important (Chang and Lee, 2004). Traditional approaches separately and sequentially consider machine scheduling and job delivery, without effective coordination between the two. However, making two individual but uncoordinated decisions will not necessarily produce a global optimal solution.

Lee and Chen (2001) studied machine scheduling problems with transportation considerations. Two types of transportation situations were considered in their paper. Type-1 was transportation of jobs from one machine to another for further processing. Type-2 was the transportation provided to delivery of finished jobs to their destinations. The following study concentrates on the delivery of finished jobs to customer(s) Type-2 transportation as defined by Lee and Chen (2001). Potts (1980) and Hall and Shmoys (1992) studied a single machine problem with unequal job arrival and delivery times. Zdrzałka (1995) and Woeginger (1998) investigated a single machine scheduling with equal job arrival times, unequal job delivery times and sequence-independent batch set-up times. Liu and Cheng (2002) considered a single machine preemptive scheduling with unequal job arrival and delivery times. Woeginger (1994) studied parallel machines with equal job arrival times and unequal job delivery times. Gharbi and Haouari (2002) considered parallel machines with unequal job arrival and delivery times. Hall and Potts (2003) introduced supply chain scheduling problems, which were characterized by coordinating scheduling, batching and delivery decisions, with the objective of minimizing the overall scheduling and delivery cost. Chen and Vairaktarakis (2005) considered a similar problem with a batch capacity limit, the single customer case and the multi-customer case with a fixed number of customers.

Lee and Chen (2001) have incorporated transportation time and vehicle capacity requirements into machine scheduling models. They analyzed the complexity of various models in which jobs were first processed by machines then delivered by one or more vehicles to a single customer. The vehicles have finite or infinite capacity and there is a transportation time for each direction of the delivery. Chang and Lee (2004) have extended Lee and Chen’s (2001) work to the situation when each job occupies a different amount of space in the vehicle. They discussed three scenarios of the problem with the makespan as the performance measure, including: (1) jobs which are processed on a single machine and delivered by a single vehicle to one customer area, (2) jobs which are processed by either one of two parallel machines and delivered by a single vehicle to one customer area and (3) jobs to be processed by a single machine and delivered by a single vehicle to two customer areas. Li et al. (2005) developed a single machine scheduling model incorporating routing decisions of a delivery vehicle serving multiple customers at different locations. Except for multiple customer locations Li et al. (2005) set the sum of job arrival times as the objective.

Chang and Lee (2004) studied, for the first time, problems in which each job might occupy differing amounts of physical space in a transport vehicle. Based on machine scheduling and finished product delivery as discussed by Chang and Lee (2004), this study deals with the situation in which jobs are processed on a single machine and delivered by multiple vehicles to one customer area. The objective is to determine the job processing sequence in the shop together with the delivery schedule to minimize makespan. This study presents a mixed binary integer programming (BIP) model for optimal makespan. Also, an illustrated example is proposed to solve the problem using the proposed model.

PROBLEM DESCRIPTION AND NOTATION DEFINITION

This study investigated a class of the two-stage scheduling problem where the first stage is job production and the second is job delivery. The investigative focus is on integrating production scheduling with delivery of finished products to a single customer area. In this problem, jobs are first processed in a single machine then delivered in batches by multiple vehicles to one customer area. Jobs require varying physical space while being loaded into a vehicle and delivered to a single customer. The vehicles are associated with a capacity constraint, measured by the total physical space of the jobs it can deliver in one trip and has a specific transportation time for each delivery. Job completion time denotes the time when a job arrives at the customer. All jobs delivered in one shipment to a single customer have the same completion times. The cost function measures the customer service level, taking production and job delivery as one system. In particular, this study aimed to minimize all jobs delivery times for the customer.

The proposed problem is described as follows. A set of n jobs, N = {J₁, J₂, …, J_n}, has first to be processed in a manufacturing system by a single machine and then delivered to a single customer. Each job, J_i, needed a processing time of p_i in the manufacturing system. Let e_i be the size of J_i, representing the physical space J_i occupied when loaded in the vehicle. Vehicle g is available for delivery, with a capacity of z_g and is first located at the manufacturing facility. Vehicle capacity is measured by the total physical space the vehicle provides for one delivery. Assuming that while the total physical space of jobs loaded does not exceed z_g, they could be arranged to fit in the physical space provided by the vehicle. A delivery batch denotes all jobs delivered together in one shipment and a transportation time is associated with each delivery batch and the vehicle. Furthermore, we define a single customer area as a location. In this study, the situation of deliveries made to one customer area with multiple vehicles is considered. Let, t^g₀₁ be the travel time from the single machine to the single customer location using the vehicle g, while t^g₁₀ be the travel time from the single customer location to the single machine using the vehicle g.

The problem is to find a schedule for processing and delivering finished jobs to the customer in the minimal time required for all jobs to be processed and delivered. For convenient analysis, the makespan of schedule σ, denoted as C_max(σ), is defined in this study as the time when the vehicle finishes delivering the last batch to the customer location and returns to the machine. To avoid ambiguity, this is simplified as C_max(σ) to C_max.

The three-field notation scheme, α|β|γ, introduced by Graham et al. (1979), is applied to represent the problems being studied. In the three-field scheme, α is the scheduling environment, β describes job characteristics or restrictive requirements and γ defines the objective function to be minimized. In the α field, Pp(Mm)→Rr represents the scheduling environment of p plants, m machines and r retailers. In the β field, v =, c_g = represents the number of vehicles and vehicle capacity. For example, P1(M1)→R1|v = G, c_g = z_g|C_max denoted the proposed problem with single-plant, single-machine, single-retailer, multiple vehicles carrying processed jobs and the total physical space of jobs loaded on vehicle g no more than z_g, with the objective of minimizing makespan

Theorem 1: The problem P1(M1)→R1|v = G, c_g = z_g|C_max is NP-hard in the strong sense.

Proof: Clearly, the problem P1(M1)→R1|v = G, c_g = z_g|C_max is strongly NP-hard since its special problem P1(M1)→R1|v = 1, c₁ = z₁|C_max is   strongly NP-hard (Chang and Lee, 2004).

The following notation was used throughout the study:

THE OPTIMIZATION MODEL

The optimization model employed mixed BIP technique to find the optimal solution for the proposed problem P1(M1)→Rr|v = G, c_g = z_g|C_max. The optimization model is described as follows:

Minimize:

(1)

Subject to:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

C_max ≥ 0; r_k ≥ 0, u_k ≥ 0, T_k ≥ 0 k = 1, 2, …, n;

y_k is binary k = 1, 2, …, n

Y_ik is binary i, k = 1, 2, …, n

(21)

The objective is found in Eq. 1. The objective is to minimize makespan of the set of orders during the time horizon. Constraint Eq. 2 ensures that each order could be processed on only one batch. Constraint set Eq. 3
ensures that:

could not equal 1 when

That is, if no orders placed at batch number k then also no orders placed at batch number k + 1. Constraint Eq. 4 ensures that y_k = 0 when:

while constraint Eq. 5 ensures that y_k = 1 when:

Hence, y_k = 1 when batch B_k is not null batch, otherwise y_k = 0 when batch B_k is null batch. Constraint Eq. 6-8 state the restrictions for the delivery batch at the vehicle. Constraint Eq. 6 restricts each batch delivered by one vehicle at most. Constraint Eq. 7 ensures that:

when y_k = 0. That is, if no jobs placed at batch number k then also no jobs delivered by all vehicles. Constraint Eq. 8 describes the relations between:

Constraint Eq. 9 restricts the total batch size to vehicle capacity, that is:

when V_kg = 1. The ready time of B_k is defined by constraint Eq. 10 and 11, that is:

when y_k = 1. Constraint Eq. 12-16 state the departure time u_k. Constraint Eq. 12 enforces u_k = 0 when y_k = 0. Constraint Eq. 13 and 14 describe the relations between u_k and r_k. Constraint Eq. 15 and 16 ensure that u_k = u_k′ + t^g₀₁ + t^g₁₀ when V_kg = V_k′g = 1. Constraint Eq. 17-19 define T_k. Constraint Eq. 17 enforces T_k = 0 when y_k = 0. Constraint Eq. 18 and 19 ensure that T_k = u_k + t^g₀₁ + t^g₁₀ when V_kg = 1. Furthermore, constraint Eq. 20 defines C_max. Finally, constraint Eq. 21 specifies the non-negativity of C_max, r_k, u_k and T_k and establishes the binary restrictions for y_k, Y_ik and V_kg.

Size complexity indicates how large a problem is in terms of binary variables, constraints and continuous (real) variables as a function of n and G, that is, the number of orders and the number of vehicles, in the problem. For the proposed optimization model, the number of binary variables is n² + nG + n, the number of constraints is n²G + 2nG + 12n - 2G + 1 and the number of continuous variables is 3n + 1.

AN ILLUSTRATIVE EXAMPLE

The proposed mixed BIP model is illustrated here. Six jobs are to be scheduled, namely J₁ to J₆. Table 1 lists the processing time, size, the capacity of vehicle and the travel time of vehicle between areas. In this example, there are six jobs, one machine, one customer area and two vehicles with different capacities. The travel time between machine and customer area depends on the vehicle. The optimization model is tested using computer programs coded in ILOG OPL language and solved with ILOG CPLEX on an Intel Core 2 Quad CPU Q6600 2.40 GHz with 1.98 GB RAM. The problem is solved by the mixed BIP formulation and its optimal makespan is 37. The related optimal schedule is shown in Fig. 1. The values of related variables follow. B₁ = {J₁, J₂}, B₂ = {J₅}, B₃ = {J₄}, B₄ = {J₃ , J₆},

Table 1:	Problem data for the example

Fig. 1:	An optimal schedule for the example

V₁₂ = 1, V₂₁ = 1, V₃₂ = 1, V₄₁ = 1, r₁ = 5, r₂ = 14, r₃ = 17, r₄ = 28, u₁ = 5, u₂ = 19, u₃ = 19, u₄ = 28, T₁ = 19, T₂ = 28, T₃ = 33, T₄ = 37, C_max = 37.

CONCLUSION AND FUTURE RESEARCH

This study considers single machine scheduling for jobs delivered to one customer area with multiple vehicles. The objective is to minimize makespan. A mixed binary integer programming model is developed to optimally solve this problem. Also, an illustrated example is proposed to find the optimal schedule using the proposed model. Future research should address problems with different shop environments, including flow-shop and job-shop. Problems with other performance measures, including minimum mean arrival time, minimum mean flow time, mean tardiness and multi-criteria measures, should also be studied. Meta-heuristics could be used to achieve solutions.