Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem

Lei Shang; Michele Garraffa; Federico Della Croce; Vincent TKindt

首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem

【24h】

Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem

机译：合并搜索树中的节点：单机总时延调度问题的精确指数算法

获取原文

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

开具论文收录证明 >>

文献代查 >>

页面导航

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

摘要

This paper proposes an exact exponential algorithm for the problem of minimizing the total tardiness of jobs on a single machine. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity is O*(2.247^n) keeping the space complexity polynomial. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties.

机译：本文提出了一种精确的指数算法，用于将单台机器上的作业的总拖延最小化。它基于众所周知的Lawler分解特性，开发了基本的分支和归约框架的结构。所提出的称为分支合并的算法是对嵌入和合并节点合并操作的分支减少技术的一种改进。它的时间复杂度为O *（2.247 ^ n），保持空间复杂度多项式。分支合并技术可能会推广到具有类似分解特性的其他测序问题。

著录项

来源
《LIPIcs : Leibniz International Proceedings in Informatics》 |2018年第23期|共12页
作者
Lei Shang; Michele Garraffa; Federico Della Croce; Vincent TKindt;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种
中图分类计算技术、计算机技术;
关键词
Exact exponential algorithmSingle machine total tardinessBranch-and-merge;

机译：精确指数算法单机总拖后处理分支合并;

相似文献

外文文献
中文文献
专利

1. An exact exponential branch-and-merge algorithm for the single machine total tardiness problem [J] . Garraffa Michele, Shang Lei, Della Croce Federico, Theoretical computer science . 2018,第期

机译：用于单机总迟到问题的精确指数分支和合并算法
2. Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups [J] . Jorge M.S. Valente, Rui A.F.S. Alves Computers & operations research . 2008,第7期

机译：具有序列相关设置的单机总加权拖延调度问题的波束搜索算法
3. A hybrid cuckoo search metaheuristic algorithm for solving single machine total weighted tardiness scheduling problems with sequence dependent setup times [J] . M.K. Marichelvam, M. Geetha International Journal of Computational Complexity and Intelligent Algorithms . 2016,第1期

机译：求解时间与序列相关的单机总加权迟到调度问题的混合杜鹃搜索元启发式算法
4. Design of Iterated Local Search Algorithms: An Example Application to the Single Machine Total Weighted Tardiness Problem [C] . Matthijs den Besten, Thomas Stutzle, Marco Dorigo European Workshop on Evolutionary Computation in Combinatorial Optimization . 2001

机译：迭代本地搜索算法的设计：对单机的示例应用程序总加权迟到问题
5. Heuristic algorithms to minimize total weighted tardiness on the single machine and identical parallel machines with sequence dependent setup and future ready time [D] . Xi, Yue 2013

机译：启发式算法，可最大程度地降低单机和相同并行机上的总加权拖尾率，并具有与序列相关的设置和未来准备时间
6. Single-Machine Scheduling to Minimize Total Completion Time and Tardiness with Two Competing Agents [O] . Wen-Chiung Lee, Yau-Ren Shiau, Yu-Hsiang Chung, -1

机译：具有两个竞争代理的单机调度可最大程度地减少总完成时间和拖延时间
7. Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups [O] . Jorge M. S. Valente 100

机译：具有序列相关设置的单机总加权延迟调度问题的波束搜索算法
8. Local Search Algorithms for a Single-Machine Scheduling Problem with Positive and211 Negative Time-Lags [R] . Hurink, J. L., Keuchel, J. 1998

机译：具有正和负时滞的单机调度问题的局部搜索算法

Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem

摘要

著录项

相似文献

相关主题

期刊订阅