贪婪策略在占线订单加工问题中的竞争分析

作者：郑斐峰; 徐寅峰

来源：系统管理学报, 2007, (04): 417-421.

• 贪婪策略
• 占线问题
• 订单排序
• 竞争比 greedy strategy
• online problem
• order scheduling
• competitive ratio

根据实际生产中订单收益随加工长度变化的一般规律,建立了占线订单加工模型,构建一种贪婪策略并分析它在本模型中的竞争性能。具体证明它在中断订单有、无惩罚两种情形下的竞争比,并讨论了模型中收益函数的参数对竞争比结果的影响。

• 单位
  西安交通大学机械制造系统工程国家重点实验室; 西安交通大学