Two-Agent Supply Chain Scheduling Problem to Minimize the Sum of the Total Weighted Completion Time and Batch Cost

被引：3

作者：

Yang L.-Y. ^{[1
]}

Lu X.-W. ^{[1
]}

机构：

[1] Department of Mathematics, East China University of Science and Technology, Shanghai

来源：

Journal of the Operations Research Society of China | 2017年 / 5卷 / 02期

基金：

中国国家自然科学基金;

关键词：

Algorithm; Supply chain scheduling; Two-agent;

D O I：

10.1007/s40305-017-0171-5

中图分类号：

学科分类号：

摘要：

Two-agent single-machine scheduling problem is considered in this paper. Agent A’s goal is to minimize the sum of the total weighted delivery time and the total delivery cost, and agent B has the delivery time window. First, the NP-hardness of the general problem is proved, and then two special cases are considered. One case is that A’s jobs have agreeable ratio and this problem is still NP-hard. A pseudo-polynomial dynamic programming algorithm and a 32-approximation algorithm are designed. In the other case, A’s jobs have agreeable ratio and B’s jobs have deadline at the same time. This problem is polynomial solvable. © 2017, Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg.

引用

页码：257 / 269

页数：12

共 18 条

[1]

Baker K.R., Smith J.C., A multiple-criterion model for machine scheduling, J. Sched., 6, 1, pp. 7-16, (2003)

[2]

Agnetis A., Billaut J.C., Gawiejnowicz S., Pacciarelli D., Soukhal A., Scheduling problems with two competing agents, Oper. Res., 52, 2, pp. 229-242, (2004)

[3]

Pacifici A., Agnetis A., Pacciarelli D., Multi-agent Scheduling: Models and Algorithms, (2014)

[4]

Perez-Gonzalez P., Framinan J.M., A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems, Eur. J. Oper. Res., 235, 1, pp. 1-16, (2014)

[5]

Orona D., Shabtayb D., Steiner G., Single machine scheduling with two competing agents and equal job processing times, Eur. J. Oper. Res., 244, 1, pp. 86-99, (2015)

[6]

Elvikis D., T'Kindt V., Two-agent scheduling on uniform parallel machines with min-max criteria, Ann. Oper. Res., 213, 1, pp. 79-94, (2014)

[7]

Ng C.T., Yuan J.J., Cheng T.C.E., Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theor. Comput. Sci., 362, 1-3, pp. 273-281, (2006)

[8]

Cheng T.C.E., Ng C.T., Yuan J.J., Multi-agent scheduling on a single machine with max-form criteria, Eur. J. Oper. Res., 188, 2, pp. 603-609, (2008)

[9]

Lee C.Y., Chen Z.L., Machine scheduling with transportation considerations, J. Sched., 4, 1, pp. 3-24, (2001)

[10]

Ji M., He Y., Cheng T.C.E., Batch delivery scheduling with batch delivery cost on a single machine, Eur. J. Oper. Res., 176, 2, pp. 745-755, (2007)

← 1 2 →