An Improved Algorithm for a Bicriteria Batching Scheduling Problem
Cheng He; Xiumei Wang; Yixun Lin; Yundong Mu
RAIRO - Operations Research - Recherche Opérationnelle (2013)
- Volume: 47, Issue: 1, page 1-8
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topHe, Cheng, et al. "An Improved Algorithm for a Bicriteria Batching Scheduling Problem." RAIRO - Operations Research - Recherche Opérationnelle 47.1 (2013): 1-8. <http://eudml.org/doc/275033>.
@article{He2013,
abstract = {This note is concerned with the bicriteria scheduling problem on a series-batching machine to minimize maximum cost and makespan. An O(n5) algorithm has been established previously. Here is an improved algorithm which solves the problem in O(n3) time.},
author = {He, Cheng, Wang, Xiumei, Lin, Yixun, Mu, Yundong},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {multicriteria scheduling; batching machine; maximum cost; pareto optimal solutions; Pareto optimal solutions},
language = {eng},
number = {1},
pages = {1-8},
publisher = {EDP-Sciences},
title = {An Improved Algorithm for a Bicriteria Batching Scheduling Problem},
url = {http://eudml.org/doc/275033},
volume = {47},
year = {2013},
}
TY - JOUR
AU - He, Cheng
AU - Wang, Xiumei
AU - Lin, Yixun
AU - Mu, Yundong
TI - An Improved Algorithm for a Bicriteria Batching Scheduling Problem
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 1
SP - 1
EP - 8
AB - This note is concerned with the bicriteria scheduling problem on a series-batching machine to minimize maximum cost and makespan. An O(n5) algorithm has been established previously. Here is an improved algorithm which solves the problem in O(n3) time.
LA - eng
KW - multicriteria scheduling; batching machine; maximum cost; pareto optimal solutions; Pareto optimal solutions
UR - http://eudml.org/doc/275033
ER -
References
top- [1] S. Albers and P. Brucker, The complexity of one-machine batching problems. Discrete Appl. Math.47 (1993) 87–107. Zbl0792.90035MR1256738
- [2] P. Brucker, Scheduling Algorithms (third edition). Springer, Berlin (2001). Zbl1060.90034MR1880405
- [3] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling : A survey. Annal. Discr. Math.5 (1979) 287–326. Zbl0411.90044MR558574
- [4] C. He, H. Lin, Y.X. Lin and J. Tian, Bicriteria scheduling on a series -batching machine to minimize maximum cost and makespan. CEJOR Cent. Eur. J. Oper. Res.21 (2013) 177–186. MR3016882
- [5] C. He, Y.X. Lin and J.J. Yuan, Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine. Found. Comput. Decision Sci.33 (2008) 369–376. Zbl1204.90039MR2500062
- [6] C. He, Y.X. Lin and J.J. Yuan, A DP algorighm for minimizing makespan and total completion time on a series-batching machine. Informat. Process. Lett.109 (2009) 603–607. Zbl1214.68096MR2508083
- [7] H. Hoogeveen, Multicriteria scheduling. European J. Oper. Res.167 (2005) 592–623. Zbl1154.90458MR2157061
- [8] J.A. Hoogeveen, Single-machine scheduling to minimize a function of two or three maximum cost criteria. J. Algorithms21 (1996) 415–433. Zbl0857.68012MR1405687
- [9] S. Webster and K.R. Baker, Scheduling groups of jobs on a single machine. Oper. Res.43 (1995) 692–703. Zbl0857.90062MR1356417
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.