Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/77588
Title: Two-agent scheduling on a single sequential and compatible batching machine
Authors: Li, S
Cheng, TCE 
Ng, CT 
Yuan, J
Keywords: Dynamic programming
FPTAS
Sequential and compatible batch
Single-machine scheduling
Two agents
Issue Date: 2017
Publisher: John Wiley & Sons
Source: Naval research logistics, 2017, v. 64, no. 8, p. 628-641 How to cite?
Journal: Naval research logistics 
Abstract: We study two-agent scheduling on a single sequential and compatible batching machine in which jobs in each batch are processed sequentially and compatibility means that jobs of distinct agents can be processed in a common batch. A fixed setup time is required before each batch is started. Each agent seeks to optimize some scheduling criterion that depends on the completion times of its own jobs only. We consider several scheduling problems arising from different combinations of some regular scheduling criteria, including the maximum cost (embracing lateness and makespan as its special cases), the total completion time, and the (weighted) number of tardy jobs. Our goal is to find an optimal schedule that minimizes the objective value of one agent, subject to an upper bound on the objective value of the other agent. For each problem under consideration, we provide either a polynomial-time or a pseudo-polynomial-time algorithm to solve it. We also devise a fully polynomial-time approximation scheme when both agents’ scheduling criteria are the weighted number of tardy jobs.
URI: http://hdl.handle.net/10397/77588
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.21779
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

2
Citations as of Sep 18, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.