Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/43469
Title: Two-agent single-machine scheduling to minimize the batch delivery cost
Authors: Yin, Y
Wang, Y
Cheng, TCE 
Wang, DJ
Wu, CC
Keywords: Batch delivery
Fully polynomial-time approximation scheme
Scheduling
Two agents
Issue Date: 2016
Publisher: Pergamon Press
Source: Computers and industrial engineering, 2016, v. 92, p. 16-30 How to cite?
Journal: Computers and industrial engineering 
Abstract: We consider integrated production and batch delivery scheduling in a make-to-order production system involving two competing agents, each of which having its own job set competes to process its jobs on a shared single machine. To save the delivery cost, the jobs of the same agent can be processed and delivered together batches. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time is incurred before the processing of the first job in each batch. Each of the agents wants to minimize an objective function depending on the completion times of its own jobs. The goal is to determine a schedule for all the jobs of the two agents that minimizes the objective function of one agent, while keeping the objective function value of the other agent below or at a given value. For each of the problems under consideration, we either provide a polynomial-time algorithm to solve it or show that it is NP-hard. In addition, for each of the NP-hard problems, we present a mixed integer linear programming (MILP) formulation and provide a pseudo-polynomial dynamic programming algorithm, establishing that it is NP-hard in the ordinary sense only, and show that it admits an efficient fully polynomial-time approximation scheme, if viable. Finally, we compare the performance of the pseudo-polynomial dynamic programming algorithms against the corresponding MILP formulations with randomly generated instances.
URI: http://hdl.handle.net/10397/43469
ISSN: 0360-8352
EISSN: 1879-0550
DOI: 10.1016/j.cie.2015.12.003
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

23
Last Week
0
Last month
Citations as of Apr 22, 2018

WEB OF SCIENCETM
Citations

22
Last Week
0
Last month
Citations as of Apr 25, 2018

Page view(s)

66
Last Week
1
Last month
Citations as of Apr 22, 2018

Google ScholarTM

Check

Altmetric


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