...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Single-machine scheduling with maintenance activities and rejection
【24h】

Single-machine scheduling with maintenance activities and rejection

机译：单机调度与维护活动和拒绝

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the single-machine scheduling with job rejection and the additional constraint that a maintenance activity of fixed length must be performed either by a deadline or in a fixed time interval. The scheduling costs of the accepted jobs are the makespan, maximum lateness, maximum tardiness, maximum weighted completion time, total (weighted) completion time, and total (weighted) number of tardy jobs. The objective of our research is to reveal the tradeoff between the scheduling cost of the accepted jobs and the total rejection cost of the rejected jobs. After showing that three problems are binary NP-hard, combining the known results in the literature, all the problems studied in this paper are binary NP-hard. Then we present pseudo-polynomial-time algorithms for solving all the problems studied in this paper. The distinctive feature of our research is that we always obtain time-complexity results by studying some related auxiliary Pareto scheduling problems. (C) 2020 Elsevier B.V. All rights reserved.
机译：我们研究了带有作业拒绝的单机调度问题，以及固定长度的维修活动必须在截止日期或固定时间间隔内执行的附加约束。接受作业的调度成本包括完工时间、最大延误、最大延误、最大加权完成时间、总（加权）完成时间和总（加权）延误作业数。我们的研究目的是揭示接受作业的调度成本和拒绝作业的总拒绝成本之间的折衷。在证明了三个问题是二元NP难的基础上，结合文献中的已知结果，本文研究的所有问题都是二元NP难问题。然后，我们提出了伪多项式时间算法来解决本文研究的所有问题。我们研究的显著特点是，我们总是通过研究一些相关的辅助帕累托调度问题来获得时间复杂度结果。（C） 2020爱思唯尔B.V.版权所有。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号