• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >An Algorithm for Single Machine Sequencing with Release Dates to Minimize Total Weighted Completion Time
【24h】

An Algorithm for Single Machine Sequencing with Release Dates to Minimize Total Weighted Completion Time

机译：具有发布日期的单机排序算法最小化总加权完成时间

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A branch and bound algorithm for a problem in operations research is derived. Each of n jobs is to be processed without interruption on a single machine which can handle only one job at a time. Each job becomes available for processing at its release date, requires a processing time, and has a positive weight. Given a processing order of the jobs, the earliest completion time for each job can be computed. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times. A heuristic is presented which is used in calculating the lower bound. The lower bound is obtained by performing a Lagrangean relaxation of the release date constraints; the Lagrange multipliers are chosen so that the sequence generated by the heuristic is an optimum solution of the relaxed problem, thus yielding a lower bound. A method to increase the lower bound by deriving improved constraints to replace the original release date constraints is given. The algorithm, which includes several dominance rules, is tested on problems with up to fifty jobs. The computational results indicate that the version of the lower bound, using improved constraints, is superior to the original version.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号