|
|||||
|
|
| 具有交货期限的占线订单加工 | |
| 引用本文： | 郑斐峰,徐寅峰,张娥.具有交货期限的占线订单加工[J].系统工程,2006,24(5):101-104. |
| 作者姓名： | 郑斐峰 徐寅峰 张娥 |
| 作者单位： | 1. 西安交通大学管理学院,陕西,西安,710049 2. 西安交通大学管理学院,陕西,西安,710049;西安交通大学机械制造系统工程国家重点实验室,陕西,西安,710049 3. 上海财经大学,信息管理与工程学院,上海,200433 |
| 基金项目： | 国家高技术研究发展计划(863计划);国家自然科学基金 |
| 摘 要： | 探讨一类占线订单加工问题，具体分析当订单交货时间具有一定上限约束时的不可中断和可中断两种模型。对于不可中断模型，证明先到先服务策略在两种不同交货期限约束时分别是最优策略与最优占线策略；对于可中断模型，提出了基于先到先服务原则的可中断策略，并证明当交货期限小于3倍加工时间时该策略具有竞争比3／2。 |
| 关 键 词： | 订单加工 占线策略 竞争比 确定性策略 |
| 文章编号： | 1001-4098（2006）05-0101-04 |
| 收稿时间： | 2006-03-07 |
| 修稿时间： | 2006-03-07 |
On-line Order Scheduling Problem with Due Date |
|
| ZHENG Fei-feng,XU Yin-feng,ZHANG E.On-line Order Scheduling Problem with Due Date[J].Systems Engineering,2006,24(5):101-104. | |
| Authors: | ZHENG Fei-feng XU Yin-feng ZHANG E |
| Abstract: | This paper investigates the on-line order scheduling problem considering due date.For non-preemptive model,(we prove) that when each order has a due date at most two times of its processing time,the FCFS strategy is optimal.(Otherwise) FCFS has a competitive ratio equal 2,which meets the lower bound for deterministic strategies in that case.For preemptive-restart model,we present a deterministic strategy called PFCFS,and also prove that it has a competitive ratio(equal) 3/2 when the due date of each order is strictly less than 3 times of the order's processing time. |
| Keywords: | Order Processing t On-line Strategy Competitive Ratio t Deterministic Strategy |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |