Hierarchical optimization on an unbounded parallel-batching machine
RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 1, pp. 55-60.

This paper studies a hierarchical optimization problem on an unbounded parallel-batching machine, in which two objective functions are maximum costs, representing different purposes of two decision-makers. By a hierarchical optimization problem, we mean the problem of optimizing the secondary criterion under the constraint that the primary criterion is optimized. A parallel-batching machine is a machine that can handle several jobs in a batch in which all jobs start and complete respectively at the same time. We present an O(n4)-time algorithm for this hierarchical scheduling problem.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017089
Classification : 90B35, 90C29
Mots-clés : Hierarchical optimization, batching machine, maximum cost
He, Cheng 1 ; Li, Li 1

1 
@article{RO_2018__52_1_55_0,
     author = {He, Cheng and Li, Li},
     title = {Hierarchical optimization on an unbounded parallel-batching machine},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {55--60},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {1},
     year = {2018},
     doi = {10.1051/ro/2017089},
     zbl = {1457.90068},
     mrnumber = {3812468},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2017089/}
}
TY  - JOUR
AU  - He, Cheng
AU  - Li, Li
TI  - Hierarchical optimization on an unbounded parallel-batching machine
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2018
SP  - 55
EP  - 60
VL  - 52
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2017089/
DO  - 10.1051/ro/2017089
LA  - en
ID  - RO_2018__52_1_55_0
ER  - 
%0 Journal Article
%A He, Cheng
%A Li, Li
%T Hierarchical optimization on an unbounded parallel-batching machine
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2018
%P 55-60
%V 52
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2017089/
%R 10.1051/ro/2017089
%G en
%F RO_2018__52_1_55_0
He, Cheng; Li, Li. Hierarchical optimization on an unbounded parallel-batching machine. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 1, pp. 55-60. doi : 10.1051/ro/2017089. http://archive.numdam.org/articles/10.1051/ro/2017089/

[1] A. Agnetis, P.B. Mirchani, D. Pacciarelli and A. Pacifici, Scheduling problems with two competing agents. Oper. Res. 52 (2004) 229–242. | DOI | Zbl

[2] A. Agnetis, J.-C. Billaut, S. Gawiejnowicz, D. Pacciarelli and A. Soukhal, Multiagent Scheduling - Models and Algorithms Problems. Springer-Verlag, Berlin (2014). | DOI | Zbl

[3] K.R. Baker and J.C. Smith, A multiple-criterion model for machine scheduling. J. Sched. 6 (2003) 7–16. | DOI | Zbl

[4] P. Brucker, Scheduling Algorithms, 4th edn. Springer-Verlag, Berlin (2004). | DOI | Zbl

[5] P. Brucker, A. Gladky, H. Hoogeveen, M.Y. Kovalyov, C.N. Potts, T. Tautenhahn et al., Scheduling a batching machine. J. Sched. 1 (1998) 31–54. | DOI | Zbl

[6] Z.C. Geng and J.J. Yuan, A note on unbounded parallel-batch scheduling. Inf. Process. Lett. 115 (2015) 969–974. | DOI | Zbl

[7] 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. Ann. Discret. Math. 5 (1979) 287–326. | DOI | Zbl

[8] C. He and H. Lin, Hierarchical optimization with double due dates on an unbounded parallel-batching machine to minimize maximum lateness. 4OR Q. J. Oper. Res. 14 (2016) 153–164. | DOI | Zbl

[9] C. He, Y.X. Lin and J.J. Yuan, Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theor. Comput. Sci. 381 (2007) 234–240. | DOI | Zbl

[10] C. He, H. Lin, J.J. Yuan and Y.D. Mu, Batching machine scheduling with bicriteria: maximum cost and makespan. Asia-Pac. J. Oper. Res. 31 (2014) 1–10. | MR | Zbl

[11] J.A. Hoogeveen, Single-machine Scheduling to minimize a function of two or three maximum cost criteria. J. Algorithms 21 (1996) 415–433. | DOI | MR | Zbl

[12] H. Hoogeveen, Multicriteria scheduling. Eur. J. Oper. Res. 167 (2005) 592–623. | DOI | MR | Zbl

[13] V. Tkindt and J.-C. Billaut, Multicriteria Scheduling: Theory, Models and Algorithms (2nd edn). Springer-Verlag, Berlin (2006). | Zbl

Cité par Sources :