New Results on Single-Machine Scheduling with Rejection to Minimize the Total Weighted Completion Time

• Autorzy: Zhang Liqi , Yu Xue , Lu Lingfa

Identyfikatory

DOI

10.2478/fcds-2024-0006

• Języki publikacji: EN

Abstrakty

EN

In this paper, we study eight single-machine scheduling problems with rejection and position-dependent parameters. We consider two position-dependent parameters as follows: (1) position-dependent weights and (2) position-dependent processing times. In addition, we also introduce a weight-modifying activity or a rate-modifying activity into our problems. In the first six problems, the task is to minimize the sum of the total weighted completion time of accepted jobs and the total rejection cost of rejected jobs. We show that all six problems can be solved in polynomial time. In the last two problems, the task is to minimize the total weighted completion time of accepted jobs under the constraint that the total rejection cost of rejected jobs can not exceed a given upper bound. We show that these two problems are binary NP-hard and each problem admits an FPTAS.

Słowa kluczowe

EN

scheduling with rejection; position-dependent parameters; dynamic programming

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2024
• Tom: Vol. 49, No. 1
• Strony: 75--94
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Zhang Liqi

• College of Information and Management Science Henan Agricultural University, China

autor

Yu Xue

• School of Mathematics and Statistics Zhengzhou University, China

autor

Lu Lingfa

• School of Mathematics and Statistics Zhengzhou University, China

Bibliografia

• [1] A. Agnetis, G. Mosheiov, Scheduling with job rejection and position-dependent processing times on proportionate flowshops. Optimization Letters 11, 885-892, 2017.
• [2] A. Bachman, A. Janiak, Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society 55, 257-264, 2004.
• [3] Y. Bartal, S. Leonardi, A.M. Spaccamela, J. Stougie, Multi-processor scheduling with rejection. SIAM Journal on Discrete Mathematics 13, 64-78, 2000.
• [4] Z. G. Cao, Z. Wang, Y. Z. Zhang, S. P. Liu, On several scheduling problems with rejection or discretely compressible processing times. Lecture Notes in Computer Science 3959, 90-98, 2006.
• [5] Y. R. Chen, Z. L. Guan, Y. C. Tsai, F. D. Chou, Single machine scheduling problem with a weight-modifying activity to minimize the total weighted completion time. IEEE Access 10, 45444-45456, 2022.
• [6] D. W. Engels, D. R. Karger, S. G. Kolliopoulos, S. Sengupta, R. N. Uma, J. Wein, Techniques for scheduling with rejection. Journal of Algorithms 49, 175-191, 2003.
• [7] M. R. Garey, D. S. Johnson. Computers and Intractablity: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.
• [8] C. Jiang, D. X. Zou, D. Y. Bai D, J. B. Wang, Proportionate flowshop scheduling with position-dependent weights. Engineering Optimization 52, 37-52, 2020.
• [9] Kahlbacher H. (1992) Termin-und Ablaufplanung-ein analytischer Zugang. Ph.D. thesis, University of Kaiserslautern
• [10] H. J. Kim, B. I. Kim, Optimal sequence for single server scheduling incorporating a rate-modifying activity under job-dependent linear deterioration. European Journal of Operational Research 298, 439-450, 2022.
• [11] Y. J. Kim, J. W. Jang, D. S. Kim, B. S. Kim, Batch loading and scheduling problem with processing time deterioration and rate-modifying activities. International Journal of Production Research 60, 1600-1620, 2022.
• [12] C.-Y. Lee, V. J. Leon, Machine scheduling with a rate-modifying activity. European Journal of Operational Research 128, 119-128, 2001
• [13] G. Mosheiov, D. Oron, A note on scheduling a rate modifying activity to minimize total late work. Computers and Industrial Engineering 154, 107138, 2021.
• [14] G. Mosheiov, D. Oron, Scheduling problems with a weight-modifying-activity. Annals of Operations Research 295, 737-745, 2020.
• [15] D. Oron, Two-agent scheduling problems under rejection budget constraints. Omega 102, 102313, 2021.
• [16] D. Shabtay, N. Gaspar, M. Kaspi, A survey on off-line scheduling with rejection. Journal of Scheduling 16, 3-28, 2013.
• [17] P. Schuurman, G. J. Woeginger. Approximation Schemes - A Tutorial. Lectures on Scheduling, LA Wolsey, 2009.
• [18] D. J. Wang, Y. Q. Yin, Y. Jin, Parallel-machine rescheduling with job unavailability and rejection. Omega 81, 246-260, 2018.
• [19] J. B. Wang, B. Cui, P. Ji, W. W. Liu, Research on single-machine scheduling with position-dependent weights and past-sequence-dependent delivery times. Journal of Combinatorial Optimization 41, 290-303, 2021.
• [20] L. O. Whitaker, Integrated production and maintenance activities. M.S. Thesis, Department of Industrial Engineering, Texas A&M University, College Station, TX, 1996.
• [21] G. J. Woeginger, When does a dynamic programming formulation guarantee the exitence of an FPTAS? INFORMS Journal of Computting 12, 57-74, 2000.
• [22] L. Q. Zhang, L. F. Lu, J. J. Yuan, Single-machine scheduling under the job rejection constraint. Theoretical Computer Science 411, 1877-1882, 2010.
• [23] X. G. Zhang, G. L. Yan, W. Z Huang, G. C. Tang, Single-machine scheduling problems with time and position dependent processing times. Annals of Operations Research 186, 345-356, 2011.
• [24] Z. G. Zhu, F. F Zheng, C. B. Chu, Multitasking scheduling problems with a ratemodifying activity. International Journal of Production Research 55, 296-312, 2017.