Fast approximation algorithm for job sequencing with deadlines
From MaRDI portal
Publication:1154384
DOI10.1016/0166-218X(81)90008-1zbMath0464.90035OpenAlexW2065104488MaRDI QIDQ1154384
Publication date: 1981
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(81)90008-1
job sequencingdeadlinesfast approximation algorithmminimization of delay penaltiespolynomial epsilon-approximation algorithmrange-and-bound method
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35)
Related Items (33)
An optimization algorithm for the clearing of interbank payments ⋮ Approximation schemes for scheduling a maintenance and linear deteriorating jobs ⋮ An approximate binary search algorithm for the multiple-choice knapsack problem ⋮ Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval ⋮ Approximate Deadline-Scheduling with Precedence Constraints ⋮ Approximation schemes for a class of subset selection problems ⋮ Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval ⋮ Improving the complexities of approximation algorithms for optimization problems ⋮ Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations ⋮ A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs ⋮ Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines ⋮ Single processor scheduling with job values depending on their completion times ⋮ A Fast Approximation Algorithm For The Subset-Sum Problem ⋮ An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem ⋮ Improving the solution complexity of the scheduling problem with deadlines: A general technique ⋮ An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs ⋮ Single machine robust scheduling with budgeted uncertainty ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates ⋮ Fast approximation algorithms for routing problems with hop-wise constraints ⋮ A dynamic programming approach to the multiple-choice multi-period knapsack problem and the recursive APL2 code ⋮ Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals ⋮ Approximation algorithms for scheduling a single machine to minimize total late work ⋮ Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date ⋮ Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains ⋮ Optimal delivery time quotation in supply chains to minimize tardiness and delivery costs ⋮ Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints ⋮ FPTAS for half-products minimization with scheduling applications ⋮ Approximation algorithms for single machine scheduling with one unavailability period ⋮ Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries ⋮ Parallel machine batching and scheduling with deadlines ⋮ Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains ⋮ Improved algorithms for single machine scheduling with release dates and rejections
Cites Work
This page was built for publication: Fast approximation algorithm for job sequencing with deadlines
