During the production process, regular maintenance is necessary and important to maintain high efficiency, because machines inevitably fail with increasing use. However, certain tasks are often neglected due to time and budget constraints, and other factors. In this regard, we propose the unrelated parallel-machine scheduling problem with maintenance and rejection penalties, wherein the ultimate objective is to minimize total cost while identifying the optimal maintenance frequencies, optimal maintenance positions, set of rejected jobs, and optimal scheduled job sequence. Considering resource constraints, the maintenance cost is controlled by the upper bound of the total maintenance frequency. Based on these factors, the optimal polynomial-time solution and its computational complexity with a fixed number of machines are presented. As an illustrative example, it was determined that the scheduling method proposed in this report is effective and practical.

1. [1] X. L. Zheng and L. Wang, “A two-stage adaptive fruit fly optimization algorithm for unrelated parallel machine scheduling problem with additional resource constraints,” Expert Systems with Applications, Vol.65, pp. 28-39, 2016.
2. [2] A. A. Qamhan and l. M. Alharkan, “Note on “A two-stage adaptive fruit fly optimization algorithm for unrelated parallel machine scheduling problem with additional resource constraints”,” Expert Systems with Applications, Vol.128, pp. 81-83, 2019.
3. [3] R. Rudek, “Scheduling problems with position dependent job processing times: computational complexity results,” Annals of Operations Research, Vol.196, No.1, pp. 491-516, 2012.
4. [4] T. Sakaguchi, K. Matsumoto, and N. Uchiyama, “Nesting scheduling in sheet metal processing based on coevolutionary genetic algorithm in different environments,” Int. J. Automation Technol., Vol.12, No.5, pp. 730-738, 2018.
5. [5] M. Asjad and S. Khan, “Analysis of maintenance cost for an asset using the genetic algorithm,” Int. J. of System Assurance Engineering and Management, Vol.8, No.2, pp. 445-457, 2016.
6. [6] E. Gustavsson, M. Patriksson, A. B. Strömberg, A. Wojciechowski, and M. Önnheim, “Preventive maintenance scheduling of multi-component systems with interval costs,” Computers & Industrial Engineering, Vol.76, pp. 390-400, 2014.
7. [7] A. O. Hopland and S. F. Kvamsdal, “Optimal maintenance scheduling for local public purpose buildings,” Property Management, Vol.34, No.2, pp. 120-135, 2016.
8. [8] H. K. Wang, H. Z. Huang, Y. F. Li, and Y. J. Yang, “Condition-based maintenance with scheduling threshold and maintenance threshold,” IEEE Trans. on Reliability, Vol.65, No.2, pp. 513-524, 2016.
9. [9] S. Gawiejnowicz and B. M. T. Lin, “Scheduling time-dependent jobs under mixed deterioration,” Applied Mathematics and Computation, Vol.216, No.2, pp. 438-447, 2010.
10. [10] P. J. Lai, W. C. Lee, and H. H. Chen, “Scheduling with deteriorating jobs and past-sequence-dependent setup times,” The Int. J. of Advanced Manufacturing Technology, Vol.54, Issues 5-8, pp. 737-741, 2011.
11. [11] D. Morita and H. Suwa, “An optimization method for critical chain scheduling toward project greenality,” Int. J. Automation Technol., Vol.6, No.3, pp. 331-337, 2012.
12. [12] B. Alidaee and N. K. Womer, “Scheduling with time dependent processing times: Review and extensions,” J. of the Operational Research Society, Vol.50, No.7, pp. 711-720, 1999.
13. [13] J.-B. Wang, L.-Y. Wang, D. Wang, X. Huang, and X.-R. Wang, “A note on single-machine total completion time problem with general deteriorating function,” The Int. J. of Advanced Manufacturing Technology, Vol.44, Issues 11-12, pp. 1213-1218, 2009.
14. [14] T. Tanizaki, H. Katagiri, and A. O. N. Rene, “Scheduling algorithms using metaheuristics for production processes with crane interference,” Int. J. Automation Technol., Vol.12, No.3, pp. 297-307, 2018.
15. [15] C. Zhao and H. Tang, “Due-window assignment for a single machine scheduling with both deterioration and positional effects,” Asia Pacific J. of Operational Research, Vol.32, No.3, 1550014, 2015.
16. [16] D. J. Wang, F. Liu, Y. Z. Wang, and Y. Jin, “A knowledge-based evolutionary proactive scheduling approach in the presence of machine breakdown and deterioration effect,” Knowledge-Based Systems, Vol.90, pp. 70-80, 2015.
17. [17] N. Yin and L. Kang, “Minimizing makespan in permutation flow shop scheduling with proportional deterioration,” Asia Pacific J. of Operational Research, Vol.32, No.6, 1550050, 2015.
18. [18] M. Cheng, S. Xiao, R. Luo, and Z. Lian, “Single-machine scheduling problems with a batch-dependent aging effect and variable maintenance activities,” Int. J. of Production Research, Vol.56, No.23, pp. 7051-7063, 2018.
19. [19] G. Schmidt, “Scheduling with limited machine availability 1,” European J. of Operational Research, Vol.121, No.1, pp. 1-15, 2000.
20. [20] Y. Ma, C. Chu, and C. Zuo, “A survey of scheduling with deterministic machine availability constraints,” Computers and Industrial Engineering, Vol.58, No.2, pp. 199-211, 2010.
21. [21] S. J. Yang and D. L. Yang, “Minimizing the total completion time in single machine scheduling with aging/deteriorating effects and deteriorating maintenance activities,” Computers & Mathematics with Applications, Vol.60, No.7, pp. 2161-2169, 2010.
22. [22] G. Mosheiov and J. B. Sidney, “Scheduling a deteriorating maintenance activity on a single machine,” J. of the Operational Research Society, Vol.61, No.5, pp. 882-887, 2010.
23. [23] T. C. E. Cheng, S. J. Yang, and D. L. Yang, “Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity,” Int. J. of Production Economics, Vol.135, No.1, pp. 154-161, 2012.
24. [24] M. Tezuka, S. Munakata, and M. Sawada, “Maintenance schedule optimization based on failure probability distribution,” Proc. of 2015 Int. Conf. on Industrial Engineering and Operations Management (IEOM), pp. 1-5, 2015.
25. [25] F. T. S. Chan, C. S. Wong, and B. Niu, “Scheduling of multi-die operations with multiple maintenance tasks,” Proc. of 2015 Int. Conf. on Industrial Engineering and Operations Management (IEOM), pp. 1-5, 2015.
26. [26] Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, and L. Stougie, “Multiprocessor scheduling with rejection,” Proc. of the 7th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA ’96), pp. 95-103, 1996.
27. [27] D. W. Engels, D. R. Karger, S. G. Kolliopoulos, S. Sengupta, R. N. Uma, and J. Wein, “Techniques for scheduling with rejection,” Proc. of European Symp. on Algorithms (ESA 1998), pp. 490-501, 1998.
28. [28] H. Mokhtari, “A nature inspired intelligent water drops evolutionary algorithm for parallel processor scheduling with rejection,” Applied Soft Computing, Vol.26, pp. 166-179, 2015.
29. [29] L. Zhang, L. Lu, and S. Li, “New results on two-machine flow-shop scheduling with rejection,” J. of Combinatorial Optimization, Vol.31, No.4, pp. 1493-1504, 2016.
30. [30] L. Epstein and H. Zebedat-Haider, “Preemptive online scheduling with rejection of unit jobs on two uniformly related machines,” J. of Scheduling, Vol.17, No.1, pp. 87-93, 2014.
31. [31] J. J. Chi, “Parallel machines scheduling with rejection and availability constraints,” J. of Qufu Normal University (Natural Science Edition), Vol.42, Issue 3, pp. 42-48, 2016.
32. [32] W. Li, J. Li, X. Zhang, and Z. Chen, “Parallel-Machine Scheduling Problem under the Job Rejection Constraint,” Int. Workshop on Frontiers in Algorithmics (FAW 2014), pp. 158-169, 2014.
33. [33] S. S. Li and R. X. Chen, “Scheduling a bounded parallel-batching machine with incompatible job families and rejection,” J. of the Operations Research Society of China, Vol.2, No.4, pp. 499-510, 2014.
34. [34] L. Nie, “Single machine scheduling problem with rejection to minimize the total earliness plus the total rejection cost,” Int. J. of Machine Learning and Computing, Vol.5, No.1, pp. 36-39, 2015.
35. [35] Q. Feng, B. Fan, S. Li, and W. Shang, “Two-agent scheduling with rejection on a single machine,” Applied Mathematical Modelling, Vol.39, Issues 3-4, pp. 1183-1193, 2014.
36. [36] D. Shabtay and D. Oron, “Proportionate flow-shop scheduling with rejection,” J. of the Operational Research Society, Vol.67, No.5, pp. 752-769, 2016.
37. [37] R. Ahmadi, “Scheduling preventive maintenance for a nonperiodically inspected deteriorating system,” Int. J. of Reliability Quality and Safety Engineering, Vol.22, No.6, 1550029, 2015.
38. [38] I. Kacem and E. Levner, “An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs,” J. of Industrial and Management Optimization, Vol.12, No.3, pp. 811-817, 2015.
39. [39] G. Mosheiov, “Parallel machine scheduling with a learning effect,” J. of the Operational Research Society, Vol.52, No.10, pp. 1165-1169, 2001.
40. [40] W. H. Kuo and D. L. Yang, “Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect,” J. of the Operational Research Society, Vol.59, No.3, pp. 416-420, 2008.
41. [41] S. J. Yang, “Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time,” Applied Mathematical Modelling, Vol.37, No.5, pp. 2995-3005, 2013.
42. [42] G. H. Hardy, J. E. Littlewood, and G. Pólya, “Inequalities,” Cambridge University Press, 1967.