Name
Title | ||
|---|---|---|
Merging Nodes in Search Trees: an Exact Exponential Algorithm for the Single Machine Total Tardiness Scheduling Problem. |
Abstract | ||
|---|---|---|
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 Lawleru0027s 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. |
Year | Venue | Field |
|---|---|---|
2017 | IPEC | Embedding,Job shop scheduling,Tardiness,Exponential function,Polynomial,Computer science,Algorithm,Merge (version control),Time complexity |
DocType | Citations | PageRank |
Conference | 1 | 0.36 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lei Shang | 1 | 1 | 0.36 |
| Michele Garraffa | 2 | 14 | 3.03 |
| Federico Della Croce | 3 | 399 | 41.60 |
| Vincent T'kindt | 4 | 203 | 21.04 |