Approximation algorithms for multi-agent scheduling to minimize total weighted completion time

被引：86

作者：

Lee, Kangbok ^{[2
]}

Choi, Byung-Cheon ^{[2
]}

Leung, Joseph Y. -T. ^{[1
]}

Pinedo, Michael L. ^{[2
]}

机构：

[1] New Jersey Inst Technol, Dept Comp Sci, Newark, NJ 07102 USA

[2] NYU, Dept Informat Operat & Management Sci, Stern Sch Business, New York, NY 10012 USA

来源：

INFORMATION PROCESSING LETTERS | 2009年 / 109卷 / 16期

关键词：

Multi-agent scheduling; Total weighted completion time; Approximation algorithm; FPTAS; Multi-Objective Shortest-Path problem; OBJECTIVES;

D O I：

10.1016/j.ipl.2009.04.018

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time Approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：913 / 917

页数：5

共 50 条

[21] On scheduling with non-increasing time slot cost to minimize total weighted completion time [J].

Yingchao Zhao ;

Xiangtong Qi ;

Minming Li .

Journal of Scheduling, 2016, 19 :759-767

[22] On scheduling with non-increasing time slot cost to minimize total weighted completion time [J].

Zhao, Yingchao ;

Qi, Xiangtong ;

Li, Minming .

JOURNAL OF SCHEDULING, 2016, 19 (06) :759-767

[23] Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time [J].

Ma, Ran ;

Yuan, Jinjiang .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2014, 158 :114-119

[24] A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time [J].

Tao, Jiping .

COMPUTERS & OPERATIONS RESEARCH, 2014, 43 :215-224

[25] Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time [J].

Li, Wenjie ;

Liu, Hailing ;

Li, Shisheng .

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2018, 35 (04)

[26] Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time [J].

Joseph Y.-T. Leung ;

Haibing Li ;

Michael Pinedo .

Annals of Operations Research, 2008, 159 :107-123

[27] A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time [J].

Tang, LX ;

Xuan, H ;

Liu, JY .

COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (11) :3344-3359

[28] Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time [J].

Leung, Joseph Y. -T. ;

Li, Haibing ;

Pinedo, Michael .

ANNALS OF OPERATIONS RESEARCH, 2008, 159 (01) :107-123

[29] Online Scheduling with Rejection to Minimize the Total Weighted Completion Time Plus the Total Rejection Cost on Parallel Machines [J].

Ma R. ;

Yuan J.-J. .

Journal of the Operations Research Society of China, 2016, 4 (1) :111-119

[30] Transportation and Batching Scheduling for Minimizing Total Weighted Completion Time [J].

Wei, Hongjun ;

Yuan, Jinjiang ;

Gao, Yuan .

MATHEMATICS, 2019, 7 (09)

← 1 2 3 4 5 →