Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-08T07:44:05.147Z Has data issue: false hasContentIssue false
  • English
  • Français

An Improved Algorithm for a Bicriteria Batching SchedulingProblem∗

Published online by Cambridge University Press:  11 February 2013

Cheng He ,
Xiumei Wang ,
Yixun Lin  and
Yundong Mu
Cheng He
Affiliation:
School of Science, Henan University of Technology, Zhengzhou, Henan 450001, China.. [email protected]
Xiumei Wang
Affiliation:
Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450001, China
Yixun Lin
Affiliation:
Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450001, China
Yundong Mu
Affiliation:
School of Science, Henan University of Technology, Zhengzhou, Henan 450001, China.. [email protected]
Get access

Abstract

This note is concerned with the bicriteria scheduling problem on a series-batchingmachine to minimize maximum cost and makespan. AnO(n5) algorithm has been establishedpreviously. Here is an improved algorithm which solves the problem inO(n3) time.

Keywords

Multicriteria schedulingbatching machinemaximum Costpareto optimal solutions
Type
Research Article
Information
RAIRO - Operations Research , Volume 47 , Issue 1 , January 2013 , pp. 1 - 8
Copyright
© EDP Sciences, ROADEF, SMAI, 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Références

Albers, S. and Brucker, P., The complexity of one-machine batching problems. Discrete Appl. Math. 47 (1993) 87–107. Google Scholar
P. Brucker, Scheduling Algorithms (third edition). Springer, Berlin (2001).
Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling : A survey. Annal. Discr. Math. 5 (1979) 287–326. Google Scholar
He, C., Lin, H., Lin, Y.X. and Tian, J., Bicriteria scheduling on a series -batching machine to minimize maximum cost and makespan. CEJOR Cent. Eur. J. Oper. Res. 21 (2013) 177–186. Google Scholar
He, C., Lin, Y.X. and Yuan, J.J., Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine. Found. Comput. Decision Sci. 33 (2008) 369–376. Google Scholar
He, C., Lin, Y.X. and Yuan, J.J., A DP algorighm for minimizing makespan and total completion time on a series-batching machine. Informat. Process. Lett. 109 (2009) 603–607. Google Scholar
Hoogeveen, H., Multicriteria scheduling. European J. Oper. Res. 167 (2005) 592–623. Google Scholar
Hoogeveen, J.A., Single-machine scheduling to minimize a function of two or three maximum cost criteria. J. Algorithms 21 (1996) 415–433. Google Scholar
Webster, S. and Baker, K.R., Scheduling groups of jobs on a single machine. Oper. Res. 43 (1995) 692–703. Google Scholar