Production, Manufacturing and LogisticsMachine scheduling with job delivery coordination
Introduction
Supply chain management has been one of the most important and widely discussed topics in manufacturing research over the last ten years. A supply chain represents all stages at which value is added to a manufactured product. Generally speaking, it includes all the interactions between suppliers, manufacturers, distributors, and customers. Due to market globalization, coordination among different stages in the supply chain to achieve ideal overall system performance has become more practical and has received attention from both industry practitioners and academic researchers.
Furthermore, with the popularity of just-in-time concepts, companies now tend to reduce their inventory levels in order to be competitive. This trend has created a closer interaction between the stages in a supply chain and has increased the practical 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 extremely important. Traditional approaches separately and sequentially consider machine scheduling and job delivery, without effective coordination between the two. However, making two decisions separately without coordination will not necessarily yield a global optimal solution. Substantial ineffectiveness may result when decision-making between the two stages is poorly coordinated, especially when transportation resources are scarce in the system.
This paper studies a class of the two-stage scheduling problem in which the first stage is job production and the second stage is job delivery. The focus is on the study of the integration of production scheduling with delivery of finished products to customers. In this problem, jobs are first processed in a manufacturing system then delivered to respective customers. Depending on specific problem characteristics, the manufacturing system can be a single machine or set of machines. The customers can possibly be located at different locations. Jobs are delivered in batches by a transporter. Jobs require varying physical space while being loaded into a transporter and delivered to respective customers. A transporter can be a truck, a specialized car, or any special resource concurrently occupied during job transport. Generically, transporters are referred to as vehicles. Each vehicle is associated with a capacity constraint, measured by the total physical space of the jobs it can deliver in one transport trip. A particular transportation time is associated with each delivery. Job completion time is defined as the time when a job arrives at the customer. All jobs delivered in one shipment to one customer have the same completion times. Considering production and job delivery as one system, the cost function is chosen to measure the customer service level. In particular, we want to minimize the time for all jobs to be delivered to the respective customer(s).
The study begins by examining a simplified version of the problem in which each job is processed by a single machine, then delivered by a single vehicle to customers located in close proximity to each other (defined as a one customer area). (Later in this paper, the problem is then generalized to the case in which jobs are processed by parallel machines and to the case when deliveries are made to two customer areas.) The one customer area assumption applies if the travel times between customers are not significant in comparison with the time from the manufacturing system to the customer or when all jobs are delivered to a regional distribution center rather than to individual customers. It is also applicable to a situation in which the manufacturer makes direct shipments to each customer. In that situation, a routing decision is not needed.
We consider a problem in which only one vehicle is available to deliver the finished jobs. It seems unrealistic to assume that there is only one vehicle to deliver the jobs since the manufacturer can easily expand its delivery capacity, if the demand exceeds this capacity, by adding more vehicles or subcontracting some of the deliveries. However, this study examines the coordination effects to gain insights for other, more complicated situations by assuming the delivery capacity to be a constraining factor. The chosen objective function is a fundamental measure of performance in classic machine-scheduling research. It provides useful information to the customer(s) on the estimated completion time for an entire work order.
The remainder of this paper is organized as follows. We briefly review the literature in Section 2. Section 3 defines the studied problems as well as the required notations. This problem is intractable even in a simplified version. We focus, therefore, on developing heuristics with guaranteed worst-case performance for some special cases of the problem. In Section 4, we study a problem in which jobs are processed by a single machine and are delivered by a single vehicle to a one customer area. Section 5 considers a similar problem but with two parallel machines in the manufacturing system. In Section 6, we discuss a problem with a single machine but with jobs that must be delivered to either one of two customer areas. Section 7 presents a conclusion as well as a discussion of future research directions.
Section snippets
Literature review
In the field of machine scheduling, most researchers have studied scheduling problems without taking into account underlying physical material handling systems. The assumption is made that an unlimited capacity is associated with the material handling system and that transportation times between machines are negligible. Only a few researchers have considered the joint optimization of machine scheduling and job transporting in the underlying material handling system. Perhaps the first study that
Problem statement and notation
The problem is described as follows. There is a set of n jobs, N={J1,J2,…,Jn}, to first be processed in a manufacturing system by a single machine and then to be delivered to the respective customers. Each job, Jj, needs a processing time of pj in the manufacturing system. Let sj be the size of Jj, which represents the physical space Jj occupies when it is loaded in the vehicle. One vehicle is available to deliver jobs, which has a capacity of z and is initially located at the manufacturing
The one-machine problem with one customer area: 1→D, k=1|v=1, c=z|Cmax
In this problem, each job must be processed by a single machine and then delivered to one customer area. Let T=2t01. Each delivery, therefore, has the same transportation time T. Note that, by our definition, Cmax=maxj{Cj}+t01. Minimizing Cmax is equivalent to minimizing maxj{Cj}, since t01 is a constant. Our purpose is to schedule jobs to minimize the makespan. Lemma 1 1→D, k=1|v=1, c=z|Cmax is NP-hard in the strong sense. Proof Let the special case of 1→D, k=1|v=1, c=z|Cmax be all jobs with zero processing
The two identical machines with one customer area problem: P2→D, k=1|v=1, c=z|Cmax
We now consider a problem similar to the one discussed in Section 4 but with two identical machines in the manufacturing system. Each job can be processed on either machine, and then delivered by a vehicle to a customer. Since 1→D, k=1|v=1, c=z|Cmax is NP-hard in the strong sense, this problem also is NP-hard in the strong sense. The following provides a heuristic algorithm justified with a worst-case analysis. Heuristic H2 Assign jobs to batches based on the FFD algorithm. Let the total number of resulting
The one machine with two customer areas problem: 1→D, k=2|v=1, c=z|Cmax
Now consider the situation in which jobs are processed on a single machine and then delivered to either area 1 or 2. Using the notation defined in Section 3, this problem is represented as 1→D,k=2|v=1,c=zCmax.
Property 1 (i) to (iv), stated in Section 4, still holds for this problem. Let T1 (T2) be the transportation time for a batch that contains only jobs that require delivery to area 1 (area 2), and let T3 be the transportation time for a batch that contains jobs that require delivery to
Conclusion and future research
This paper considers machine scheduling and finished product delivery together. In particular, the work addresses the situation in which jobs require different amounts of storage space during delivery. Three scenarios of the problem are discussed. For the problem in which jobs are processed on a single machine and delivered by a single vehicle to one customer area (Section 4), a proof of NP-hardness and a heuristic, justified by a worst-case analysis, are provided. The worst-case performance
Acknowledgements
The authors would like to thank the three anonymous referees for their constructive comments on an earlier draft of this paper. This research was supported in part by Research Grants Council of Hong Kong under Grant: HKUST 6010/02E.
References (28)
Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs
European Journal of Operational Research
(1996)- et al.
Single machine scheduling with batch deliveries
European Journal of Operational Research
(1996) - et al.
Optimization and approximation in deterministic sequencing and scheduling: A survey
Annals of Discrete Mathematics
(1979) - et al.
On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date
European Journal of Operational Research
(1993) - et al.
Makespan minimization for flow-shop problems with transportation times
Discrete Applied Mathematics
(2001) - et al.
Scheduling with batching: A review
European Journal of Operational Research
(2000) A note on the complexity of single-machine scheduling with a common due date, earliness–tardiness, and batch delivery costs
European Journal of Operational Research
(1996)- et al.
Batching and scheduling jobs on batch and discrete processors
Operations Research
(1992) - et al.
The Logic of Logistics
(1997) - et al.
Design and operational issues in AGV-served manufacturing systems
Annals of Operations Research
(1998)
Computers and Intractability: A Guide to the Theory of NP-Completeness
Scheduling a two-machine flowshop with travel times to minimize maximum lateness
International Journal of Production Research
Jackson's rule for single-machine scheduling: Making a good heuristic better
Mathematics of Operations Research
Cited by (221)
Flow shop scheduling problems with transportation constraints revisited
2024, Theoretical Computer ScienceA review on integrated scheduling and outbound vehicle routing problems
2023, European Journal of Operational ResearchThe mobile production vehicle routing problem: Using 3D printing in last mile distribution
2023, European Journal of Operational ResearchUnrelated parallel machine scheduling with eligibility constraints and delivery times to minimize total weighted tardiness
2023, Computers and Operations ResearchCoordinated scheduling of the outsourcing, in-house production and distribution operations
2022, European Journal of Operational ResearchHybrid metaheuristics for the integrated and detailed scheduling of production and delivery operations in no-wait flow shop systems
2022, Computers and Industrial Engineering