On an extension of the Sort \& Search method with application to scheduling theory

DOI10.1016/J.TCS.2013.05.023MaRDI QIDQ392015zbMATH OpenOpenAlexFDO

Authors Mathieu Liedloff, Vincent T'kindt, Ch. Lenté, A. Soukhal

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.05.023

zbMATH Keywords

schedulingexponential-time algorithmssort \& search

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Searching and sorting (68P10)

Recommendations

• Algorithmic Applications in Management
• A minimal algorithm for the multiple-choice knapsack problem
• scientific article; zbMATH DE number 3906215
• Generalized multifit-type methods. II
• scientific article; zbMATH DE number 4091174

Cites work

• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Computational geometry. Algorithms and applications.
• Computing Partitions with Applications to the Knapsack Problem
• Exact exponential algorithms.
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling
• Scheduling algorithms
• Scheduling partially ordered jobs faster than \(2^{n }\)

Cited in

(12)

• Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
• Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
• New algorithms for minimizing the weighted number of tardy jobs on a single machine
• A characterization of optimal multiprocessor schedules and new dominance rules
• Exact exponential algorithms for 3-machine flowshop scheduling problems
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work
• Extending Graham's result on scheduling to other heuristics
• An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
• On the optimality of exact and approximation algorithms for scheduling problems
• Minimizing the number of tardy jobs in two-machine settings with common due date
• Moderate exponential-time algorithms for scheduling problems

This page was built for publication: On an extension of the Sort \& Search method with application to scheduling theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392015)