Scheduling around a small common due date
The single machine scheduling problem with prohibited interruptions is considered. Job \(J_ i\) has a given processing time \(p_ i\), weight \(w_ i\) and (common to all jobs) deadline \(d<\sum^ n_{i=1} p_ i\), \(n\) denoting the number of jobs. The aim is to find such a schedule \(S\) minimizing the weighted sum of deviations of completion times of jobs from the due date \(f(S)=\sum^ n_{i=1} w_ i| C_ i-d|\), where \(C_ i\) is the completion time of the job \(J_ i\) in the schedule \(S\). A pseudo-polynomial algorithm is proposed; it requires \(O(n^ 2 d)\) time and \(O(nd)\) space. The NP-hardness of the problem is established for the case \(w_ i=w\), \(i=1,2,\dots,n\). Two polynomial solvable cases are presented: \(p_ i=p\) and \(p_ i=w_ i\) (in both cases there is no the restriction \(d<\sum^ n_{i=1} p_ i\)).
- Optimal scheduling of jobs about a common due date on a single machine
- Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
- Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
- scientific article; zbMATH DE number 853068
- Scheduling to minimize weighted earliness and tardiness about a common due-date
- Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date
- Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
- scientific article; zbMATH DE number 4059106 (Why is no real title available?)
- Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date
- Minimizing mean absolute deviation of completion times about a common due date
- Minimizing the average deviation of job completion times about a common due date
- One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
- Sequencing with Earliness and Tardiness Penalties: A Review
- Single-machine scheduling to minimize absolute deviation of completion times from a common due date
- Non-approximability of just-in-time scheduling
- Scheduling to minimize weighted earliness and tardiness about a common due-date
- On the general solution for a class of early/tardy problems
- A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems
- A note on minimizing the weighted sum of tardy and early completion penalties in a single machine: A case of small common due date
- Scheduling about a common due date with job-dependent asymmetric earlines and tardiness penalties
- Effects of change of scale on optimality in a scheduling model with priorities and earliness/tardiness penalties
- The determination of the optimal component input numbers for the completion of a single manufacturing order
- A survey of the state-of-the-art of common due date assignment and scheduling research
- On the complexity of the single machine scheduling problem minimizing total weighted delay penalty
- Minimizing total earliness and tardiness for common due date single-machine scheduling with an unavailability interval
- Heuristic and exact algorithms for the two-machine just in time job shop scheduling problem
- Common due date assignment and scheduling with ready times
- Parallel machine earliness and tardiness scheduling with proportional weights
- An improved dynamic programming algorithm for the single-machine mean absolute deviation problem with a restrictive common due date
- The weighted common due date single machine scheduling problem revisited
- The symmetric quadratic knapsack problem: approximation and scheduling applications
- Minimizing weighted earliness-tardiness on a single machine with a common due date using quadratic models
- A fully polynomial time approximation scheme for weighted job-dependent earliness-tardiness problem with agreeable ratios
- \textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
- Scheduling jobs with a V-shaped time-dependent processing time
- Dominance inequalities for scheduling around an unrestrictive common due date
- Single-machine common due date total earliness/tardiness scheduling with machine unavailability
- Scheduling with controllable release dates and processing times: total completion time minimization
- Exponential neighborhood search for a parallel machine scheduling problem
- Multicriteria scheduling
- Punctuality and idleness in just-in-time scheduling
- Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
- Just-in-time scheduling with equal-size jobs
- A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process
- Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics
- Determination of fault-tolerant fabric-cutting schedules in a just-in-time apparel manufacturing environment
- Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack
- Optimal scheduling of jobs about a common due date on a single machine
- New Lower and Upper Bounds for Scheduling Around a Small Common Due Date
- Stochastic single machine scheduling with an exponentially distributed due date
- Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates
- On scheduling around large restrictive common due windows
- Parallel-machine scheduling with weighted earliness-tardiness and optional job rejection
- Mixed integer formulations using natural variables for single machine scheduling around a common due date
- A sequential exchange approach for minimizing earliness-tardiness penalties of single-machine scheduling with a common due date
This page was built for publication: Scheduling around a small common due date
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1183621)