# 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

top## How 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 ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.