Minimising total weighted completion time for semi-online single machine scheduling with known arrivals and bounded processing times

References

• Allahverdi, A., E. Pesch, M. Pinedo, and F. Werner. 2018. “Scheduling in Manufacturing Systems: New Trends and Perspectives.” International Journal of Production Research 56 (19): 6333–6335. doi:10.1080/00207543.2018.1504252.
   Web of Science ®Google Scholar
• Anderson, E. J., and C. N. Potts. 2004. “Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time.” Mathematics of Operations Research 29 (3): 686–697. doi:10.1287/moor.1040.0092.
   Web of Science ®Google Scholar
• Asadollahi-Yazdi, E., P. Couzon, N. Q. Nguyen, Y. Ouazene, and F. Yalaoui. 2020. “Industry 4.0: Revolution Or Evolution?” American Journal of Operations Research 10 (06): 241–268. doi:10.4236/ajor.2020.106014.
   Google Scholar
• Belouadah, H., M. E. Posner, and C. N. Potts. 1992. “Scheduling with Release Dates on a Single Machine to Minimize Total Weighted Completion Time.” Discrete Applied Mathematics 36 (3): 213–231. doi:10.1016/0166-218X(92)90255-9.
   Web of Science ®Google Scholar
• Chen, B., A. Van-Vliet, and G. J. Woeginger. 1994. “New Lower and Upper Bounds for on-line Scheduling.” Operations Research Letters 16 (4): 221–230. doi:10.1016/0167-6377(94)90071-X.
   Web of Science ®Google Scholar
• Dauzère-Pérès, S., and J. B. Lasserre. 2002. “On the Importance of Sequencing Decisions in Production Planning and Scheduling.” International Transactions in Operational Research 9 (6): 779–793. doi:10.1111/itor.2002.9.issue-6.
   Google Scholar
• Davis, W. J., and A. T. Jones. 1988. “A Real-time Production Scheduler for a Stochastic Manufacturing Environment.” International Journal of Computer Integrated Manufacturing 1 (2): 101–112. doi:10.1080/09511928808944350.
   Google Scholar
• Dolgui, A., V. Kotov, A. Nekrashevich, and A. Quilliot.. 2018. “General Parametric Scheme for the Online Uniform Machine Scheduling Problem with Two Different Speeds.” Information Processing Letters 134: 18–23. doi:10.1016/j.ipl.2018.01.009.
   Web of Science ®Google Scholar
• Dolgui, A., V. Kotov, and A. Quilliot. 2015. “A Parametric Scheme for Online Uniform-machine Scheduling to Minimize the Makespan.” Buletinul Academiei De Ştiinţe a Moldovei Matematica 79 (3): 102–109. https://ibn.idsi.md/ro/vizualizare_articol/44846.
   Google Scholar
• Dwibedy, D., and R. Mohanty. 2022. “Semi-online Scheduling: A Survey.” Computers & Operations Research 139: 105646. doi:10.1016/j.cor.2021.105646.
   Web of Science ®Google Scholar
• Epstein, L.. 2018. “A Survey on Makespan Minimization in Semi-online Environments.” Journal of Scheduling 21 (3): 269–284. doi:10.1007/s10951-018-0567-z.
   Web of Science ®Google Scholar
• Fiat, A., and G. J. Woeginger. 1998. “Competitive Analysis of Algorithms.” In Online Algorithms, 1–12. Springer.
   Google Scholar
• Goemans, M. X.. 1997. “Improved Approximation Algorthims for Scheduling with Release Dates.” In Proceedings of the eighth annual ACM-SIAM Symposium on Discrete Algorithms, 591–598.
   Google Scholar
• Grabot, B., and L. Geneste. 1994. “Dispatching Rules in Scheduling Dispatching Rules in Scheduling: a Fuzzy Approach.” The International Journal of Production Research 32 (4): 903–915. doi:10.1080/00207549408956978.
   Web of Science ®Google Scholar
• Graham, R. L.. 1966. “Bounds for Certain Multiprocessing Anomalies.” Bell System Technical Journal 45 (9): 1563–1581. doi:10.1002/bltj.1966.45.issue-9.
   Google Scholar
• Hall, N. G., and M. E. Posner. 2001. “Generating Experimental Data for Computational Testing with Machine Scheduling Applications.” Operations Research 49 (6): 854–865. doi:10.1287/opre.49.6.854.10014.
   Web of Science ®Google Scholar
• Hall, N. G., M. E. Posner, and C. N. Potts. 2009. “Online Scheduling with Known Arrival Times.” Mathematics of Operations Research 34 (1): 92–102. doi:10.1287/moor.1080.0346.
   Web of Science ®Google Scholar
• Hall, L. A., A. S. Schulz, D. B. Shmoys, and J. Wein. 1997. “Scheduling to Minimize Average Completion Time: Off-line and on-line Approximation Algorithms.” Mathematics of Operations Research 22 (3): 513–544. doi:10.1287/moor.22.3.513.
   Web of Science ®Google Scholar
• Hoogeveen, J. A., and A. P. A. Vestjens. 1996. “Optimal On-Line Algorithms for Single-Machine Scheduling.” In International Conference on Integer Programming and Combinatorial Optimization, 404–414. Springer.
   Google Scholar
• Jiang, Z., S. Yuan, J. Ma, and Q. Wang. 2022. “The Evolution of Production Scheduling From Industry 3.0 Through Industry 4.0.” International Journal of Production Research 60 (11): 3534–3554. doi:10.1080/00207543.2021.1925772.
   Web of Science ®Google Scholar
• Lai, T. C., Y. N. Sotskov, N. G. Egorova, and F. Werner. 2018. “The Optimality Box in Uncertain Data for Minimising the Sum of the Weighted Job Completion Times.” International Journal of Production Research 56 (19): 6336–6362. doi:10.1080/00207543.2017.1398426.
   Web of Science ®Google Scholar
• Lenstra, J. K., A. H. G. Rinnooy-Kan, and P. Brucker. 1977. “Complexity of Machine Scheduling Problems.” In Annals of Discrete Mathematics, Vol. 1, 343–362. Elsevier.
   Google Scholar
• Nouinou, H., T. Arbaoui, and A. Yalaoui. 2022. “Minimizing Total Weighted Completion Times for Semi-online Single Machine Scheduling.” IFAC-PapersOnLine 55 (10): 2191–2196. doi:10.1016/j.ifacol.2022.10.033.
   Google Scholar
• Parente, M., G. Figueira, P. Amorim, and A. Marques. 2020. “Production Scheduling in the Context of Industry 4.0: Review and Trends.” International Journal of ProductionResearch 58 (17): 5401–5431. doi:10.1080/00207543.2020.1718794.
   Web of Science ®Google Scholar
• Phillips, C., C. Stein, and J. Wein. 1998. “Minimizing Average Completion Time in the Presence of Release Dates.” Mathematical Programming 82 (1-2): 199–223. doi:10.1007/BF01585872.
   Web of Science ®Google Scholar
• Posner, M. E.. 1985. “Minimizing Weighted Completion Times with Deadlines.” Operations Research 33 (3): 562–574. doi:10.1287/opre.33.3.562.
   Web of Science ®Google Scholar
• Reid, R. D., and N. R. Sanders. 2019. Operations Management: An Integrated Approach. New York: John Wiley & Sons.
   Google Scholar
• Russell, R. S., and B. W. Taylor. 2006. Operations Management: Quality and Competitiveness in a Global Environment. Hoboken, NJ: John Wiley & Sons Incorporated.
   Google Scholar
• Sotskov, Y. N., and N. G. Egorova. 2019. “The Optimality Region for a Single-machine Scheduling Problem with Bounded Durations of the Jobs and the Total Completion Time Objective.” Mathematics 7 (5): 382. doi:10.3390/math7050382.
   Web of Science ®Google Scholar
• Sotskov, Y. N., N. G. Egorova, and T. C. Lai. 2009. “Minimizing Total Weighted Flow Time of a Set of Jobs with Interval Processing Times.” Mathematical and Computer Modelling 50 (3-4): 556–573. doi:10.1016/j.mcm.2009.03.006.
   Web of Science ®Google Scholar
• Tan, Z., and A. Zhang. 2013. “Online and Semi-online Scheduling.” Handbook of Combinatorial Optimization 2191–2252. doi:10.1007/978-1-4419-7997-1.
   Google Scholar
• Tao, J., Z. Chao, and Y. Xi. 2009. “A Novel Way to Analyze Competitive Performance of Online Algorithms.” In Proceedings of the International MultiConference of Engineers and Computer Scientists, Vol. 1.
   Google Scholar
• Tian, J., R. Fu, and J. Yuan. 2014. “Online Over Time Scheduling on Parallel-batch Machines: a Survey.” Journal of the Operations Research Society of China 2 (4): 445–454. doi:10.1007/s40305-014-0060-0.
   Google Scholar
• Uma, R. N., J. Wein, and D. P. Williamson. 2006. “On the Relationship Between Combinatorial and LP-based Lower Bounds for NP-hard Scheduling Problems.” Theoretical Computer Science 361 (2-3): 241–256. doi:10.1016/j.tcs.2006.05.013.
   Web of Science ®Google Scholar