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.
Accepté le :
DOI : 10.1051/ro/2017089
Mots-clés : Hierarchical optimization, batching machine, maximum cost
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2017089/
[1] Scheduling problems with two competing agents. Oper. Res. 52 (2004) 229–242. | DOI | Zbl
, , and ,[2] Multiagent Scheduling - Models and Algorithms Problems. Springer-Verlag, Berlin (2014). | DOI | Zbl
, , , and ,[3] A multiple-criterion model for machine scheduling. J. Sched. 6 (2003) 7–16. | DOI | Zbl
and ,[4] Scheduling Algorithms, 4th edn. Springer-Verlag, Berlin (2004). | DOI | Zbl
,[5] Scheduling a batching machine. J. Sched. 1 (1998) 31–54. | DOI | Zbl
, , , , , et al.,[6] A note on unbounded parallel-batch scheduling. Inf. Process. Lett. 115 (2015) 969–974. | DOI | Zbl
and ,[7] Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5 (1979) 287–326. | DOI | Zbl
, , and ,[8] 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
and ,[9] Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theor. Comput. Sci. 381 (2007) 234–240. | DOI | Zbl
, and ,[10] Batching machine scheduling with bicriteria: maximum cost and makespan. Asia-Pac. J. Oper. Res. 31 (2014) 1–10. | MR | Zbl
, , and ,[11] Single-machine Scheduling to minimize a function of two or three maximum cost criteria. J. Algorithms 21 (1996) 415–433. | DOI | MR | Zbl
,[12] Multicriteria scheduling. Eur. J. Oper. Res. 167 (2005) 592–623. | DOI | MR | Zbl
,[13] Multicriteria Scheduling: Theory, Models and Algorithms (2nd edn). Springer-Verlag, Berlin (2006). | Zbl
and ,Cité par Sources :