期刊
COMPUTERS & OPERATIONS RESEARCH
卷 133, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2021.105329
关键词
Scheduling; Single-machine; Two AGENTS; Total late work; Job-rejection; Dynamic programming
类别
资金
- Israel Science Foundation [2505/19]
- Charles I. Rosen Chair of Management, The Hebrew University, Jerusalem, Israel
- Recanati Fund of The School of Business Administration, The Hebrew University, Jerusalem, Israel
This study examines a single-machine scheduling problem involving two competing agents, with a focus on minimizing total late work and limiting job costs within a specified upper bound. An innovative pseudo-polynomial dynamic programming algorithm is introduced and tested on large-size instances, proving its effectiveness. The research also extends to job rejection scenarios, with modifications made to the algorithm for solving medium-size instances efficiently.
We study a single-machine scheduling problem with two competing agents. The objective function of one agent is minimizing total late work, whereas the maximum cost of the jobs of the second agent cannot exceed a given upper bound. We introduce and test a pseudo-polynomial dynamic programming algorithm for this NP-hard problem. Our tests indicate that the algorithm can handle large-size instances (containing hundreds of jobs) fairly quickly. We then extend the setting to that of job rejection, where the scheduler may decide to process only a subset of the jobs. The dynamic programming algorithm is modified accordingly, and our numerical tests verify that medium-size instances (containing less than 100 jobs) are solved in reasonable time.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据