This paper studies the two-agent scheduling on a bounded parallel-batching machine. In the problem, there are two agents A and B each having their own job sets with the restriction that the processing times of jobs of agent B are equal. The jobs of different agents can be processed in a common batch. Moreover, each agent has its own objective function to be minimized. The objective function of agent A is the makespan of its jobs, and the objective function of agent B is the maximum lateness of its jobs. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.
Qi Feng, Wei-Ping Shang, Cheng-Wen Jiao, Wen-Jie Li
. Two-Agent Scheduling on a Bounded Parallel-Batching Machine with Makespan and Maximum Lateness Objectives[J]. Journal of the Operations Research Society of China, 2020
, 8(1)
: 189
-196
.
DOI: 10.1007/s40305-019-00258-9
[1] Baker,K.R.,Smith,J.C.:A multiple-criterion model for machine scheduling.J.Sched. 6,7-16(2003)
[2] Agnetis, A., Mirchandani, P.B.:Pacciarelli, Dario, Pacifici, Andrea:Scheduling problems with two competing agents. Oper. Res. 52, 229-242(2004)
[3] Perez-Gonzalez,P.,Framinan,J.M.:A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs:multi-agent scheduling problems[J]. Eur. J. Oper. Res. 235, 1-16(2014)
[4] Agnetis, A., Billaut, J.C., Gawiejnowicz, S., Pacciarelli, D., Soukhal, A.:Multiagent Scheduling:Models and Algorithms. Springer, Berlin (2014)
[5] Feng, Q., Fan, B., Li, S., Shang, W.:Two-agent scheduling with rejection on a single machine. Appl. Math. Model 38, 1183-1193(2015)
[6] Yuan, J.:Complexities of some problems on multi-agent scheduling on a single machine. J. Oper. Res. Soc. China 4, 379-384(2016)
[7] Li, S., Chen, R., Feng, Q.:Scheduling two job families on a single machine with two competitive agents. J. Comb. Optim. 32, 784-799(2016)
[8] Li,D.,Lu,X.:Two-agent parallel-machine scheduling with rejection.Theor.Comput.Sci. 703,66-75(2017)
[9] Lee, C.Y., Uzsoy, R., Martin-Vega, L.A.:Efficient algorithms for scheduling semiconductor burn-in operations. Oper. Res. 40, 764-775(1992)
[10] Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, Mikhail Y., Potts, C., Tautenhahn, T., Van de Velde, S.:Scheduling a batching machine. J. Sched. 1, 31-54(1998)
[11] Brucker, P., Knust, S.:Complexity results for scheduling problem. http://www.informatik.uniosnabrueck.de/knust/class/(2009)
[12] He, C., Lin, Y., Yuan, J.:Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theor. Comput. Sci. 381, 234-240(2007)
[13] Liu, L.L., Ng, C.T., Cheng, T.C.E.:Bicriterion scheduling with equal processing times on a batch processing machine. Comput. Oper. Res. 36, 110-118(2009)
[14] Sabouni, M.T.Y., Jolai, F.:Optimal methods for batch processing problem with makespan and maximum lateness objectives[J]. Appl. Math. Model. 34, 314-324(2010)
[15] Feng, Q., Yuan, J.:Liu, Hai-Ling, He, Cheng:A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives[J]. Appl. Math. Model 37, 7071-7076(2013)
[16] Gao, Y., Yuan, J., Ng, C.T., Cheng, T.C.E.:A further study on two-agent parallel-batch scheduling with release dates and deteriorating jobs to minimize the makespan[J]. Eur. J. Oper. Res. 273, 74-81(2019)
[17] Graham, R.L., Lawer, E.L., Lenstra, J., Kan, A.H.G.R.:Optimization and approximation in deterministic sequencing and scheduling:a survey. Ann. Discret. Math. 5, 287-326(1979)
[18] Tian, J., Fu, R., Yuan, J.:On-line scheduling with delivery time on a single batch machine. Theor. Comput. Sci. 374, 49-57(2007)
