A fully polynomial-time approximation scheme for total completion time minimization on a single machine with DeJong's learning effect and an availability constraint

References

• Ameni, A., E. Meriem, and B. S. Lamjed. 2018. “Scheduling Problems Under Learning Effects: Classification and Cartography.” International Journal of Production Research 56: 1642–1661. doi: 10.1080/00207543.2017.1355576
   Web of Science ®Google Scholar
• Biskup, D. 1999. “Single Machine Scheduling with Learning Effects.” European Journal of Operational Research 115: 173–178. doi: 10.1016/S0377-2217(98)00246-X
   Web of Science ®Google Scholar
• Biskup, D. 2008. “A State-of-the-Art Review on Scheduling with Learning Considerations.” European Journal of Operational Research 188: 315–329. doi: 10.1016/j.ejor.2007.05.040
   Web of Science ®Google Scholar
• Browne, S., and U. Yechiali. 1990. “Scheduling Deteriorating Jobs on a Single Processor.” Operations Research 38: 495–498. doi: 10.1287/opre.38.3.495
   Web of Science ®Google Scholar
• Cheng, T. C. E., and G. Q. Wang. 2000. “Single Machine Scheduling with Learning Effect Considerations.” Annals of Operations Research 98: 273–290. doi: 10.1023/A:1019216726076
   Web of Science ®Google Scholar
• DeJong, J. R. 1957. “The Effects of Increasing Skill on Cycle Time and its Consequences for Time Standards.” Ergonomics 1: 51–60. doi: 10.1080/00140135708964571
   Web of Science ®Google Scholar
• Dondeti, V. R., and B. B. Mohanty. 1998. “Impact of Learning and Fatigue Factors on Single Machine Scheduling with Penalties for Tardy Jobs.” European Journal of Operational Research 105: 509–524. doi: 10.1016/S0377-2217(97)00070-2
   Web of Science ®Google Scholar
• Gawiejnowicz, S. 1996. “A Note on Scheduling on a Single Processor with Speed Dependent on a Number of Executed Jobs.” Information Processing Letters 57: 297–300. doi: 10.1016/0020-0190(96)00021-X
   Web of Science ®Google Scholar
• Gawiejnowicz, S. 2007. “Scheduling Deteriorating Jobs Subject to Job or Machine Availability Constraints.” European Journal of Operational Research 180: 472–478. doi: 10.1016/j.ejor.2006.04.021
   Web of Science ®Google Scholar
• Gupta, J. N. D., and S. K. Gupta. 1988. “Single Facility Scheduling with Nonlinear Processing Times.” Computers and Industrial Engineering 14: 387–393. doi: 10.1016/0360-8352(88)90041-1
   Web of Science ®Google Scholar
• Ho, Kevin I.-J., Joseph Y.-T. Leung, and W.-D. Wei. 1993. “Complexity of Scheduling Tasks with Time-Dependent Execution Times.” Information Processing Letters 48 (6): 315–320. doi:10.1016/0020-0190(93)90175-9.
   Web of Science ®Google Scholar
• Ji, M., Y. He, and T. C. E. Cheng. 2006. “Scheduling Linear Deteriorating Jobs with an Availability Constraint on a Single Machine.” Theoretical Computer Science 362: 115–126. doi: 10.1016/j.tcs.2006.06.006
   Web of Science ®Google Scholar
• Ji, M., X. Y. Tang, X. Zhang, and T. C. E. Cheng. 2016. “Machine Scheduling with Deteriorating Jobs and DeJong's Learning Effect.” Computers & Industrial Engineering 91: 42–47. doi: 10.1016/j.cie.2015.10.015
   Web of Science ®Google Scholar
• Ji, M., D. L. Yao, Q. Y. Yang, and T. C. E. Cheng. 2015. “Machine Scheduling with DeJong's Learning Effect.” Computers & Industrial Engineering 80: 195–200. doi: 10.1016/j.cie.2014.12.009
   Web of Science ®Google Scholar
• Kacem, I., and H. Kellerer. 2018. “Approximation Schemes for Minimizing the Maximum Lateness on a Single Machine with Release Times Under Non-Availability or Deadline Constraints.” Algorithmica 80 (12): 3825–3843. doi: 10.1007/s00453-018-0417-6
   Web of Science ®Google Scholar
• Kacem, I., M. Sahnoune, and G. Schmidt. 2017. “Strongly Fully Polynomial Time Approximation Scheme for the Weighted Completion Time Minimization Problem on Two-Parallel Zcapacitated machines.” RAIRO–Operations Research 51 (4): 1177–1188. doi: 10.1051/ro/2017044
   Web of Science ®Google Scholar
• Kovalyov, M. Y., and W. Kubiak. 1998. “A Fully Polynomial Approximation Scheme for Minimizing Makespan of Deteriorating Jobs.” Journal of Heuristics 3: 287–297. doi: 10.1023/A:1009626427432
   Google Scholar
• Kovalyov, M. Y., and W. Kubiak. 1999. “A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem.” Operations Research 47: 757–761. doi:10.1287/opre.47.5.757.
   Web of Science ®Google Scholar
• Lee, C. Y. 1996. “Machine Scheduling with an Availability Constraint.” Journal of Global Optimization 9: 363–382. doi: 10.1007/BF00121681
   Web of Science ®Google Scholar
• Lee, C. Y., and S. D. Liman. 1993. “Capacitated Two-Parallel Machines Scheduling to Minimize Sum of Job Completion Times.” Discrete Applied Mathematics 41: 211–222. doi: 10.1016/0166-218X(90)90055-H
   Web of Science ®Google Scholar
• Li, S. S., and R. X. Chen. 2017. “Common Due Date Assignment and Cumulative Deterioration Scheduling on a Single Machine.” Engineering Optimization 49 (6): 976–989. doi:10.1080/0305215X.2016.1227616.
   Web of Science ®Google Scholar
• Lu, Y.-Y., and J.-Y. Liu. 2018. “A Note on Resource Allocation Scheduling with Position-Dependent Workloads.” Engineering Optimization 50 (10): 1810–1827. doi: 10.1080/0305215X.2017.1414207
   Web of Science ®Google Scholar
• Lu, Y.-Y., J.-B. Wang, P. Ji, and H. He. 2017. “A Note on Resource Allocation Scheduling with Group Technology and Learning Effects on a Single Machine.” Engineering Optimization 49 (9): 1621–1632. doi: 10.1080/0305215X.2016.1265305
   Web of Science ®Google Scholar
• Ma, Y., C. B. Chu, and C. R. Zuo. 2010. “A Survey of Scheduling with Deterministic Machine Availability Constraints.” Computers & Industrial Engineering 58: 199–211. doi: 10.1016/j.cie.2009.04.014
   Web of Science ®Google Scholar
• Okolowski, D., and S. Gawiejnowicz. 2010. “Exact and Heuristic Algorithms for Parallel-Machine Scheduling with DeJong's Learning Effect.” Computers & Industrial Engineering 59: 272–279. doi: 10.1016/j.cie.2010.04.008
   Web of Science ®Google Scholar
• Pinedo, M. 2008. Scheduling: Theory, Algorithms, and Systems. Upper Saddle River, NJ: Prentice-Hall.
   Google Scholar
• Wang, J. B. 2009. “Single Machine Scheduling with Learning Effect and Deteriorating Jobs.” Computers & Industrial Engineering 57 (4): 1452–1456. doi:10.1016/j.cie.2009.07.015.
   Web of Science ®Google Scholar
• Wang, J. B., and X. X. Liang. 2019. “Group Scheduling with Deteriorating Jobs and Allotted Resource Under Limited Resource Availability Constraint.” Engineering Optimization 51 (2): 231–246. doi: 10.1080/0305215X.2018.1454442
   Web of Science ®Google Scholar
• Wright, T. P. 1936. “Factors Affecting the Cost of Airplanes.” Journal of Aeronautical Sciences 3: 122–128. doi: 10.2514/8.155
   Google Scholar
• Yin, Y. Q., W. H. Wu, T. C. E. Cheng, and C. C. Wu. 2015. “Single-Machine Scheduling with Time-Dependent and Position-Dependent Deteriorating Jobs.” International Journal of Computer Integrated Manufacturing 28: 781–790. doi: 10.1080/0951192X.2014.900872
   Web of Science ®Google Scholar
• Yin, Y. Q., D. H. Xu, K. B. Sun, and H. X. Li. 2009. “Some Scheduling Problems with General Position-Dependent and Time-Dependent Learning Effects.” Information Sciences 179: 2416–2425. doi: 10.1016/j.ins.2009.02.015
   Web of Science ®Google Scholar
• Yin, Y. Q., D. S. Ye, and G. C. Zhang. 2014. “Single Machine Batch Scheduling to Minimize the Sum of Total Flow Time and Batch Delivery Cost with an Unavailability Interval.” Information Sciences 274: 310–322. doi: 10.1016/j.ins.2014.02.142
   Web of Science ®Google Scholar
• Zhang, X. G., W. C. Lin, W. H. Wu, and C. C. Wu. 2017. “Single-Machine Common/Slack Due Window Assignment Problems with Linear Decreasing Processing Times.” Engineering Optimization 49 (9): 1388–1400. doi: 10.1080/0305215X.2016.1248180
   Web of Science ®Google Scholar
• Zhao, C. L., J. Fang, T. C. E. Cheng, and M. Ji. 2017. “A Note on the Time Complexity of Machine Scheduling with DeJong's Learning Effect.” Computers & Industrial Engineering 112: 447–449. doi: 10.1016/j.cie.2017.08.010
   Web of Science ®Google Scholar
• Zhao, Chuan-Li, and Chou-Jung Hsu. 2017. “Scheduling Deteriorating Jobs with Machine Availability Constraints to Minimize the Total Completion Time.” Journal of Industrial and Production Engineering 34 (5): 323–329. doi:10.1080/21681015.2017.1295404.
   Web of Science ®Google Scholar
• Zhao, Chuanli, and Chou-Jung Hsu. 2019. “Fully Polynomial-Time Approximation Scheme for Single Machine Scheduling with Proportional-Linear Deteriorating Jobs.” Engineering Optimization. doi:10.1080/0305215X.2018.1558446.
   Web of Science ®Google Scholar