A new graphical approach for solving single-machine scheduling problems approximately

References

• Bechara, S. B., and M. J. Magazine. 1981. “Myopic Heuristics for Single Machine Scheduling Problems.” International Journal of Production Research 19 (1): 85–95.
   Web of Science ®Google Scholar
• Benmansour, R., H. Allaoui, and A. Artiba. 2012. “Stochastic Single Machine Scheduling with Random Common Due Date.” International Journal of Production Research 50 (13): 3560–3571.
   Web of Science ®Google Scholar
• Chubanov, S., M. Y. Kovalyov, and E. Pesch. 2006. “An FPTAS for a Single-item Capacitated Economic Lot-sizing Problem with Monotone Cost Structure.” Mathematical Programming Series A 106: 453–466.
   Web of Science ®Google Scholar
• Du, J., and Y.-T. Leung. 1990. “Minimizing Total Tardiness on One Processor is NP-hard.” Mathematics of Operations Research 15: 483–495.
   Web of Science ®Google Scholar
• Fathi, Y., and H. W. L. Nuttle. 1990. “Heuristics for the Common Due Date Weighted Tardiness Problem.” IEE Transactions 22: 215–225.
   Web of Science ®Google Scholar
• Gafarov, E. R., A. Dolgui, A. Lazarev, and F. Werner. 2013. “A Graphical Approach for Solving Single Machine Scheduling Problems Approximately.” In Proceedings of the IFAC Conference on Manufacturing Modelling, Management and Control (MIM2013), edited by N. Bakhtadze, A. Dolgui and V. Lototsky, 1340–1345. St Petersburg, Russia: Elsevier Science, June 19–21, IFAC-PapersOnline.net (ISSN 1474–6670).
   Google Scholar
• Gafarov, E. R., A. A. Lazarev, and F. Werner. 2010. A Modification of Dynamic Programming Algorithms to Reduce the Time Complexity. Preprint 20/10, FMA, OvGU Magdeburg.
   Google Scholar
• Gafarov, E. R., A. A. Lazarev, and F. Werner. 2012a. “Transforming a Pseudo-polynomial Algorithm for the Single Machine Total Tardiness Maximization Problem into a Polynomial One.” Annals of Operations Research 196 (1): 247–261.
   Web of Science ®Google Scholar
• Gafarov, E. R., A. A. Lazarev, and F. Werner. 2012b. “A Note on a Single Machine Scheduling Problem with Generalized Total Tardiness Objective Function.” Information Processing Letters 112 (3): 72–76.
   Web of Science ®Google Scholar
• Gafarov, E. R., A. A. Lazarev, and F. Werner. 2013. “Single Machine Total Tardiness Maximization Problems: Complexity and Algorithms.” Annals of Operations Research 207 (1): 121–136.
   Web of Science ®Google Scholar
• Hoogeveen, H., and V. T’Kindt. 2010. “Minimizing the Number of Late Jobs When the Starting Time of the Machine is Variable.” In Proceedings PMS, 235–238.
   Google Scholar
• Kacem, I. 2010. “Fully Polynomial Time Approximation Scheme for the Total Weighted Tardiness Minimization with a Common Due Date.” Discrete Applied Mathematics 158: 1030–1040.
   Web of Science ®Google Scholar
• Kellerer, H., and V. A. Strusevich. 2006. “A Fully Polynomial Approximation Scheme for the Single Machine Weighted Total Tardiness Problem with a Common Due Date.” Theoretical Computer Science 369: 230–238.
   Web of Science ®Google Scholar
• Koulamas, C. 2010. “The Single-machine Total Tardiness Scheduling Problem: Review and Extensions.” European Journal of Operational Research 202: 1–7.
   Web of Science ®Google Scholar
• Kovalyov, M. Y. 1995. “Improving the Complexities of Approximation Algorithms for Optimization Problems.” Operations Research Letters 17: 85–87.
   Web of Science ®Google Scholar
• Lawler, E. L. 1977. “A Pseudopolynomial Algorithm for Sequencing Jobs to Minimize Total Tardiness.” Annals of Discrete Mathematics 1: 331–342.
   Google Scholar
• Lawler, E. L. 1982. “A Fully Polynomial Approximation Scheme for the Total Tardiness Problem.” Operations Research Letters 1: 207–208.
   Google Scholar
• Lawler, E. L., and J. M. Moore. 1969. “A Functional Equation and its Application to Resource Allocation and Sequencing Problems.” Management Science 16 (1): 77–84.
   Web of Science ®Google Scholar
• Lazarev, A. A. 2007. “Solution of the NP-hard Total Tardiness Minimization Problem in Scheduling Theory.” Computational Mathematics and Mathematical Physics 47: 1039–1049.
   Google Scholar
• Lazarev, A. A., and E. R. Gafarov. 2006. “Special Case of the Single-machine Total Tardiness Problem is NP-hard.” Journal of Computer and Systems Sciences International 45 (3): 450–458.
   Web of Science ®Google Scholar
• Lazarev, A. A., A. G. Kvaratskheliya, and E. R. Gafarov. 2007. “Algorithms for Solving the NP-hard Problem of Minimizing Total Tardiness for a Single Machine.” Doklady Mathematics 75 (1): 130–134.
   Web of Science ®Google Scholar
• Maccarthy, B. L., and J. Liu. 1993. “Addressing the Gap in Scheduling Research: A Review of Optimization and Heuristic Methods in Production Scheduling.” International Journal of Production Research 31 (1): 59–79.
   Web of Science ®Google Scholar
• Maxwell, W. L. 1964. “The Scheduling of Single Machine Systems: A Review.” International Journal of Production Research 3 (3): 177–199.
   Google Scholar
• Potts, C. N., and L. N. Van Wassenhove. 1982. “A Decomposition Algorithm for the Single Machine Total Tardiness Problem.” Operations Research Letters 1: 363–377.
   Google Scholar
• Szwarc, W., F. Della Croce, and A. Grosso. 1999. “Solution of the Single Machine Total Tardiness Problem.” Journal of Scheduling 2: 55–71.
   Google Scholar
• Tanaev, V. S., V. S. Gordon, and Y. M. Shafransky. 1994. Scheduling Theory: Single-stage Systems. Dordrecht: Springer, 372p.
   Google Scholar
• Wang, S., and M. Liu. 2013. “A Branch and Bound Algorithm for Single-machine Production Scheduling Integrated with Preventive Maintenance Planning.” International Journal of Production Research 51 (3): 847–868.
   Web of Science ®Google Scholar
• Yuan, J. 1992. “The NP-hardness of the Single Machine Common Due Date Weighted Tardiness Problem.” Systems Science and Mathematical Sciences 5: 328–333.
   Google Scholar