Single machine scheduling problem with batch setups involving positional deterioration effects and multiple rate-modifying activities. (English) Zbl 1523.90152
Summary: This article considers a single machine scheduling problem with batch setups, positional deterioration effects, and multiple optional rate-modifying activities to minimize the total completion time. This problem is formulated as an integer quadratic programming problem. In view of the complexity of optimally solving this problem, a two-phase heuristic algorithm is proposed where an optimal but non-integer solution is obtained in the first phase by solving a continuous relaxed version of the problem. This solution serves as a lower bound for the optimal value of the total completion time. The second phase of the algorithm generates an integer solution using a simple rounding scheme that is optimum or very close to optimum for this problem. Empirical evaluation and comparison with an existing heuristic algorithm show that the proposed heuristic algorithm is substantially more effective in solving large-size problem instances.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C10 | Integer programming |
| 90C20 | Quadratic programming |
Keywords:
single machine scheduling with batch setups; unit processing times; positional deterioration effects; rate-modifying maintenance activities; total completion timeReferences:
| [1] | Alidaee, B.; Womer, N. K., Scheduling with Time Dependent Processing Times: Review and Extensions, Journal of the Operational Research Society, 50, 7, 711-720 (1999) · Zbl 1054.90542 · doi:10.1057/palgrave.jors.2600740 |
| [2] | Allahverdi, Ali., The Third Comprehensive Survey on Scheduling Problems with Setup Times/Costs, European Journal of Operational Research, 246, 2, 345-378 (2015) · Zbl 1347.90031 · doi:10.1016/j.ejor.2015.04.004 |
| [3] | Arigliano, Anna; Ghiani, Gianpaolo; Grieco, Antonio; Guerriero, Emanuela, Single-Machine Time-Dependent Scheduling Problems with Fixed Rate-Modifying Activities and Resumable Jobs, 4OR, 15, 2, 201-215 (2017) · Zbl 1369.90070 · doi:10.1007/s10288-016-0333-z |
| [4] | Browne, Sid; Yechiali, Uri, Scheduling Deteriorating Jobs on a Single Processor, Operations Research, 38, 3, 495-498 (1990) · Zbl 0703.90051 · doi:10.1287/opre.38.3.495 |
| [5] | Brucker, Peter; Kovalyov, Mikhail Y., Single Machine Batch Scheduling to Minimize the Weighted Number of Late Jobs, Mathematical Methods of Operations Research, 43, 1, 1-8 (1996) · Zbl 0842.90058 · doi:10.1007/BF01303431 |
| [6] | Cheng, T. C. E.; Ding, Q.; Lin, B. M. T., A Concise Survey of Scheduling with Time-Dependent Processing Times, European Journal of Operational Research, 152, 1, 1-13 (2004) · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8 |
| [7] | Cheng, T. C. E.; Gordon, Valery S.; Kovalyov, Mikhail Y., Single Machine Scheduling with Batch Deliveries, European Journal of Operational Research, 94, 2, 277-283 (1996) · Zbl 0947.90579 · doi:10.1016/0377-2217(96)00127-0 |
| [8] | Cheng, T. C. E.; Janiak, Adam; Kovalyov, Mikhail Y., Single Machine Batch Scheduling with Resource Dependent Setup and Processing Times, European Journal of Operational Research, 135, 1, 177-183 (2001) · Zbl 1077.90525 · doi:10.1016/S0377-2217(00)00312-X |
| [9] | Cheng, T. C. E.; Wu, Chin-Chia; Lee, Wen-Chiung, Some Scheduling Problems with Deteriorating Jobs and Learning Effects, Computers & Industrial Engineering, 54, 4, 972-982 (2008) · doi:10.1016/j.cie.2007.11.006 |
| [10] | Chung, Byung Do; Kim, Byung Soo, A Hybrid Genetic Algorithm with Two-Stage Dispatching Heuristic for a Machine Scheduling Problem with Step-Deteriorating Jobs and Rate-Modifying Activities, Computers & Industrial Engineering, 98, 113-124 (2016) · doi:10.1016/j.cie.2016.05.028 |
| [11] | Chung, Tsui-Ping; Liao, Ching-Jong, An Immunoglobulin-Based Artificial Immune System for Solving the Hybrid Flow Shop Problem, Applied Soft Computing, 13, 8, 3729-3736 (2013) · doi:10.1016/j.asoc.2013.03.006 |
| [12] | Gupta, J. N. D., M-Stage Scheduling Problem—a Critical Appraisal, The International Journal of Production Research, 9, 2, 267-281 (1971) · doi:10.1080/00207547108929878 |
| [13] | Gupta, Jatinder N. D.; Gupta, Sushil K., Single Facility Scheduling with Nonlinear Processing Times, Computers & Industrial Engineering, 14, 4, 387-393 (1988) · doi:10.1016/0360-8352(88)90041-1 |
| [14] | Ji, Min; Cheng, T. C. E., Batch Scheduling of Simple Linear Deteriorating Jobs on a Single Machine to Minimize Makespan, European Journal of Operational Research, 202, 1, 90-98 (2010) · Zbl 1173.90407 · doi:10.1016/j.ejor.2009.05.021 |
| [15] | Ji, Min; He, Yong; Cheng, T. C. E., Single-Machine Scheduling with Periodic Maintenance to Minimize Makespan, Computers & Operations Research, 34, 6, 1764-1770 (2007) · Zbl 1159.90404 |
| [16] | Ji, Min; Yang, Qinyun; Yao, Danli; Cheng, T. C. E., Single-Machine Batch Scheduling of Linear Deteriorating Jobs, Theoretical Computer Science, 580, 36-49 (2015) · Zbl 1311.90047 |
| [17] | Karmarkar, Uday S.; Kekre, Sham; Kekre, Sunder; Freeman, Susan, Lot-Sizing and Lead-Time Performance in a Manufacturing Cell, Interfaces, 15, 2, 1-9 (1985) · doi:10.1287/inte.15.2.1 |
| [18] | Lawler, E. L.; Lenstra, J. K.; Rinnooy-Kan, A. H. G.; Shmoys, D. B., Sequencing and Scheduling: Algorithms and Complexity, Handbooks in Operations Research and Management Science, 4, 445-522 (1993) · doi:10.1016/S0927-0507(05)80189-6 |
| [19] | Lee, Wen-Chiung., Single-Machine Scheduling with Past-Sequence-Dependent Setup Times and General Effects of Deterioration and Learning, Optimization Letters, 8, 1, 135-144 (2014) · Zbl 1288.90031 · doi:10.1007/s11590-012-0481-9 |
| [20] | Lee, C.-Y.; Leon, V. J., Machine Scheduling with a Rate-Modifying Activity, European Journal of Operational Research, 128, 1, 119-128 (2001) · Zbl 0983.90020 |
| [21] | Liu, Feng, Yang, Jing, and Lu, Yuan-Yuan. 2018. “Solution Algorithms for Single-Machine Group Scheduling with Ready Times and Deteriorating Jobs.” Engineering Optimization. doi:10.1080/0305215X.2018.1500562. |
| [22] | Melouk, Sharif; Damodaran, Purushothaman; Chang, Ping-Yu, Minimizing Makespan for Single Machine Batch Processing with Non-Identical Job Sizes Using Simulated Annealing, International Journal of Production Economics, 87, 2, 141-147 (2004) · doi:10.1016/S0925-5273(03)00092-6 |
| [23] | Mor, Baruch; Mosheiov, Gur, Batch Scheduling with a Rate-Modifying Maintenance Activity to Minimize Total Flowtime, International Journal of Production Economics, 153, 238-242 (2014) · Zbl 1348.90291 · doi:10.1016/j.ijpe.2014.03.004 |
| [24] | Mosheiov, Gur; Sarig, Assaf, Scheduling a Maintenance Activity to Minimize Total Weighted Completion-Time, Computers & Mathematics with Applications, 57, 4, 619-623 (2009) · Zbl 1165.90465 · doi:10.1016/j.camwa.2008.11.008 |
| [25] | Santos, Cipriano; Magazine, Michael, Batching in Single Operation Manufacturing Systems, Operations Research Letters, 4, 3, 99-103 (1985) · Zbl 0572.90051 · doi:10.1016/0167-6377(85)90011-2 |
| [26] | Shabtay, Dvir., The Single Machine Serial Batch Scheduling Problem with Rejection to Minimize Total Completion Time and Total Rejection Cost, European Journal of Operational Research, 233, 1, 64-74 (2014) · Zbl 1339.90153 |
| [27] | Strusevich, Vitaly A.; Rustogi, Kabir, Scheduling with Time-Changing Effects and Rate-Modifying Activities (2017), Cham, Switzerland: Springer International Publishing, Cham, Switzerland · Zbl 1357.90003 |
| [28] | Wang, Ji-Bo; Wang, Cheng, Single-Machine Due-Window Assignment Problem with Learning Effect and Deteriorating Jobs, Applied Mathematical Modelling, 35, 8, 4017-4022 (2011) · Zbl 1221.90050 · doi:10.1016/j.apm.2011.02.023 |
| [29] | Wang, Zhenyou; Xiao, Cuntao; Lin, Xianwei; Lu, Yuan-Yuan, Single Machine Total Absolute Differences Penalties Minimization Scheduling with a Deteriorating and Resource-Dependent Maintenance Activity, The Computer Journal, 61, 1, 105-110 (2018) · doi:10.1093/comjnl/bxx044 |
| [30] | Zhang, Xingong; Lin, Win-Chin; Wu, Wen-Hsiang; Wu, Chin-Chia, Single-Machine Common/Slack Due Window Assignment Problems with Linear Decreasing Processing Times, Engineering Optimization, 49, 8, 1388-1400 (2017) · doi:10.1080/0305215X.2016.1248180 |
| [31] | Zhang, Xingong; Wu, Wen-Hsiang; Lin, Win-Chin; Wu, Chin-Chia, Machine Scheduling Problems under Deteriorating Effects and Deteriorating Rate-Modifying Activities, Journal of the Operational Research Society, 69, 3, 439-448 (2018) · doi:10.1057/s41274-017-0200-0 |
| [32] | Zhang, Xingong; Yin, Yunqiang; Wu, Chin-Chia, Scheduling with Non-Decreasing Deterioration Jobs and Variable Maintenance Activities on a Single Machine, Engineering Optimization, 49, 1, 84-97 (2017) |
| [33] | Zhu, Zhanguo; Zheng, Feifeng; Chu, Chengbin, Multitasking Scheduling Problems with a Rate-Modifying Activity, International Journal of Production Research, 55, 1, 296-312 (2017) · doi:10.1080/00207543.2016.1208852 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
