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

DOI10.1016/J.TCS.2013.05.023zbMATH Open1358.68084OpenAlexW2010662359MaRDI QIDQ392015FDOQ392015

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

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

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)

Cites Work

• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Title not available (Why is that?)
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Exact exponential algorithms.
• Computational geometry. Algorithms and applications.
• Scheduling
• Scheduling algorithms
• Computing Partitions with Applications to the Knapsack Problem
• 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)