SINGLE MACHINE SCHEDULING WITH JOB DELIVERY TO MINIMIZE MAKESPAN
Authors:
- 1 February 2008
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Asia-Pacific Journal of Operational Research
- Vol. 25 (01) , 1-10
Abstract
In the single machine scheduling problem with job delivery to minimize makespan, jobs are processed on a single machine and delivered by a capacitated vehicle to their respective customers. We first consider the special case with a single customer, that is, all jobs have the same transportation time. Chang and Lee (2004) proved that this case is strongly NP-hard. They also provided a heuristic with the worst-case performance ratio [ ], and pointed out that no heuristic can have a worst-case performance ratio less than [ ] unless P = NP. In this paper, we provide a new heuristic which has the best possible worst-case performance ratio [ ]. We also consider an extended version in which the jobs have non-identical transportation times and the transportation time of a delivery batch is defined as the maximum transportation time of the jobs contained in it. We provide a heuristic with the worst-case performance ratio 2 for the extended version, and show that this bound is tight.Keywords
This publication has 14 references indexed in Scilit:
- Machine scheduling with deliveries to multiple customer locationsEuropean Journal of Operational Research, 2005
- Integrated Scheduling of Production and Distribution OperationsManagement Science, 2005
- The Coordination of Scheduling and Batch DeliveriesAnnals of Operations Research, 2005
- Improved Algorithms for Two Single Machine Scheduling ProblemsLecture Notes in Computer Science, 2005
- Machine scheduling with job delivery coordinationEuropean Journal of Operational Research, 2004
- Machine scheduling with transportation considerationsJournal of Scheduling, 2001
- Single machine scheduling with batch deliveriesEuropean Journal of Operational Research, 1996
- Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costsEuropean Journal of Operational Research, 1996
- On scheduling to minimize earliness-tardiness and batch delivery costs with a common due dateEuropean Journal of Operational Research, 1993
- Optimal two‐ and three‐stage production schedules with setup times includedNaval Research Logistics Quarterly, 1954