A Batch Scheduling Problem with Two Agents

In this paper, we consider a two-agent batch scheduling problem on a single machine such that the processing times of agent 1 and the due date of agent 2 in the same batch are identical. The objective is to minimize the total completion time of agent 1 with a constraint on the maximum tardiness of a...

Full description

Saved in:
Bibliographic Details
Published in:Asia-Pacific journal of operational research 2015-12, Vol.32 (6), p.1550044
Main Authors: Choi, Byung-Cheon, Park, Myoung-Ju
Format: Article
Language:English
Subjects:
Algorithms
Batch processing
Completion time
Operations research
Production scheduling
Scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we consider a two-agent batch scheduling problem on a single machine such that the processing times of agent 1 and the due date of agent 2 in the same batch are identical. The objective is to minimize the total completion time of agent 1 with a constraint on the maximum tardiness of agent 2. First, we propose the optimality conditions. Then, we show that the problem is strongly NP-hard. Finally, we prove the problem remains NP-hard even for the case with one batch of agent 2, and develop a pseudo-polynomial algorithm and an approximation algorithm for this case.
ISSN:0217-5959
1793-7019
0217-5959
DOI:10.1142/S021759591550044X