Minimizing flowtime and missed due-dates in single-machine sequencing
The author discusses a single machine sequencing problem to minimize an objective function consisting of weighted sum of flowtime and earliness/tardiness values of each job. The main purpose of the discussed objective function is to consider a compromise between minimizing flowtime and missed due dates which reflect the customer satisfaction. The author shows that the problem belongs to the class of NP-hard problems by reducing a more restricted, but still NP-hard, sequencing problem - the Total Discrepancy Problem - to the recognition version of the discussed problem. Justified by this complexity result, the author uses a dynamic programming approach following the method of \textit{M. Held} and \textit{R. M. Karp} [SIAM J. Appl. Math. 10, 196-210 (1962; Zbl 0106.141)]. For this algorithmic approach \(n\cdot 2^{n-1}\) subproblems must be solved to find an optimal solution. Compared with an enumerative approach, which needs n! computations, the proposed approach is more efficient. But, of course, due to its exponential complexity the use of the algorithm is limited to medium size problems (up to 20 jobs).
- Dynamic programming and decomposition approaches for the single machine total tardiness problem
- scientific article; zbMATH DE number 4123514
- Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
- A single-machine problem with multiple criteria
- scientific article; zbMATH DE number 3850790
- A new branch and bound algorithm for minimizing the weighted number of tardy jobs
- A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time
- A note on efficient sequences with respect to total flow time and number of tardy jobs
- Optimal Assignment of Total-work-content Due-dates and Sequencing in a Single-machine Shop
- An improved earliness--tardiness timing algorithm
- A Dynamic Programming Approach to Sequencing Problems
- A Generalized Model of Optimal Due-Date Assignment by Linear Programming
- scientific article; zbMATH DE number 4059106 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2146482 (Why is no real title available?)
- scientific article; zbMATH DE number 3401694 (Why is no real title available?)
- 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
- Minimizing the average deviation of job completion times about a common due-date: An extension
- Minimizing the sum of absolute lateness in single-machine and multimachine scheduling
- One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
- Single- and multiple-processor models for minimizing completion time variance
- Survey of scheduling research involving due date determination decisions
- The art and theory of dynamic programming
- A dominant subset of V-shaped sequences for a class of single machine sequencing problems
- Algorithms for mixed-model sequencing with due date restrictions
- On the monotonicity of the critical time in the constrained-degree percolation model
- BICRITERIA SCHEDULING ON SINGLE-MACHINE WITH INVENTORY OPERATIONS
- MINIMIZING TOTAL TARDINESS FOR SINGLE MACHINE SEQUENCING
- Optimal TWK-power due-date determination and sequencing
- scientific article; zbMATH DE number 4185378 (Why is no real title available?)
- Bicriterion scheduling with equal processing times on a batch processing machine
This page was built for publication: Minimizing flowtime and missed due-dates in single-machine sequencing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2640435)
