An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

Tian J.; Cheng T.C.E.; Ng C.T.; Yuan J.

首页> 外文期刊>Discrete Applied Mathematics >An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

【24h】

An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

机译：带有交货时间的单批并行机器调度的改进在线算法

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We study an on-line single parallel-batch machine scheduling problem where each job has a processing time and a delivery time. Jobs arrive over time and the batch capacity is unbounded. Jobs can be processed in a common batch, and each job is delivered independently and immediately at its completion time on the machine. The objective is to minimize the time by which all the jobs are delivered. We provide an on-line algorithm with a competitive ratio 22-1≈1.828, which improves on a 2-competitive on-line algorithm for this problem in the literature.

机译：我们研究在线单并行批处理机器调度问题，其中每个作业都有处理时间和交付时间。作业会随着时间的推移而到达，并且批处理容量不受限制。可以批量处理作业，每个作业在完成时立即在计算机上独立交付。目的是最大程度地缩短交付所有作业的时间。我们提供了一种竞争率为22-1≈1.828的在线算法，该算法在文献中针对该问题的2竞争在线算法上进行了改进。

著录项

来源
《Discrete Applied Mathematics》 |2012年第8期|共20页
作者
Tian J.; Cheng T.C.E.; Ng C.T.; Yuan J.;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
Competitive ratio; Delivery times; On-line scheduling; Parallel-batch machine;

机译：竞争比;交货时间;在线调度;并行批处理机;

相似文献

外文文献
中文文献
专利

1. An improved on-line algorithm for single parallel-batch machine scheduling with delivery times [J] . Tian J., Cheng T.C.E., Ng C.T., Discrete Applied Mathematics . 2012,第7a8期

机译：带有交货时间的单批并行机器调度的改进在线算法
2. A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times [J] . Jinjiang Yuan, Shisheng Li, Ji Tian, Journal of Combinatorial Optimization . 2009,第2期

机译：交货时间受限的单机并行批生产调度的最佳在线算法
3. An on-line algorithm for the single machine unbounded parallel-batching scheduling with large delivery times [J] . Ji Tian, Ruyan Fu, Jinjiang Yuan Information Processing Letters . 2011,第21a22期

机译：具有大交付时间的单机无限制并行批处理调度的在线算法
4. A Best On-line Algorithm for Single Machine Scheduling the Equal Length Jobs with the Special Chain Precedence and Delivery Time [C] . Cunchang Gu, Yundong Mu International conference on graphic and image processing . 2013

机译：具有特殊链优先级和交付时间的单机调度等长作业的最佳在线算法
5. Algorithms for scheduling parallel batch processing machines with non-identical job ready times. [D] . Velez Gallego, Mario Cesar. 2009

机译：用于调度具有不同作业准备时间的并行批处理机器的算法。
6. Hybrid Pareto artificial bee colony algorithm for multi-objective single machine group scheduling problem with sequence-dependent setup times and learning effects [O] . Lei Yue, Zailin Guan, Ullah Saif, -1

机译：具有序列依赖建立时间和学习效果的多目标单机群调度问题的混合帕累托人工蜂群算法
7. An improved on-line algorithm for single parallel-batch machine scheduling with delivery times [O] . Tian, J, Cheng, TCE, Ng, CT, 2012

机译：带有交付时间的单批并行机器调度的改进在线算法
8. Optimal On-Line Algorithms for Single-Machine Scheduling [R] . Hoogeveen, J. A., Vestjens, A. P. A. 1995

机译：单机调度的最优在线算法

An improved on-line algorithm for single parallel-batch machine scheduling with delivery times

摘要

著录项

相似文献

相关主题

期刊订阅