| 带有固定区间的单机双代理可中断总误工问题 |
| |
| 引用本文： | 陈秋宏,张新功.带有固定区间的单机双代理可中断总误工问题[J].运筹学学报,2019,23(1):61-71. |
| |
| 作者姓名： | 陈秋宏 张新功 |
| |
| 作者单位： | 重庆师范大学数学科学学院, 重庆 401331 |
| |
| 基金项目： | 国家自然科学基金（Nos.11571321，715610007），贵州省教育厅项目（No.14zd007），重庆市科委自然科学基金（No.cstc2018jcyjAX0631） |
| |
| 摘 要： | 研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.
|
| 关 键 词： | 单台机器 两个代理 总误工 固定时间窗口 |
| 收稿时间： | 2017-10-11 |
Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine |
| |
| CHEN Qiuhong,ZHANG Xingong.Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine[J].OR Transactions,2019,23(1):61-71. |
| |
| Authors: | CHEN Qiuhong ZHANG Xingong |
| |
| Institution: | College of Mathematics Science, Chongqing Normal University, Chongqing 400047, China |
| |
| Abstract: | This paper considers two agent scheduling problems with fixed time windows on a single machine. The jobs of the first agent might be preemptive. There exists agreeable condition with release time and due data. The objective function is to minimize the total tardiness. The focus is to find an optimal sequence that minimizes the objective of the first agent, while keeping all jobs of the second agent schedule within fixed time windows. By block principle, we present a pseudo-polynomial time dynamic programming algorithm when fixed time window equals the processing time. If the fixed time windows is larger than the processing time, we give the time complexity of the proposed problem. |
| |
| Keywords: | single scheduling two-agent total tardiness fixed time windows |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
