Production, Manufacturing and Logistics
Machine scheduling with job delivery coordination

https://doi.org/10.1016/S0377-2217(03)00364-3Get rights and content

Abstract

This paper considers together machine scheduling and finished product delivery. In particular, it 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, we provide a proof of NP-hardness and a heuristic with worst-case analysis. The worst-case performance ratio for our heuristic is proven to be 5/3, and the bound is tight. For the problem in which jobs are processed by either one of two parallel machines and delivered by a single vehicle to one customer area, our heuristic could cause at most 100% error under the worst-case with the bound being tight. For the problem that considers jobs to be processed by a single machine and delivered by a single vehicle to two customer areas, we provide another heuristic that is 100% error bound.

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

  • Step 1:

    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)

  • M.R. Garey et al.

    Computers and Intractability: A Guide to the Theory of NP-Completeness

    (1979)
  • D.D. Gemmill et al.

    Scheduling a two-machine flowshop with travel times to minimize maximum lateness

    International Journal of Production Research

    (1997)
  • L.A. Hall et al.

    Jackson's rule for single-machine scheduling: Making a good heuristic better

    Mathematics of Operations Research

    (1992)
  • Hall, N.G., Potts, C.N., 2000. Supply chain scheduling: Batching and delivery. Working Paper, Department of Management...
  • Cited by (221)

    View all citing articles on Scopus
    View full text