Due-window assignment scheduling problems with position-dependent weights on a single machine. (English) Zbl 1523.90212
Summary: This article deals with an integrated optimization problem of production scheduling and common due-window assignment on a single machine. The objective is to minimize the total cost, which is a weighted sum function of earliness and tardiness, due-window starting time, and due-window size, where the weights only depend on their position in a sequence (i.e. position-dependent weights). A polynomial time solution algorithm is provided for the corresponding problem. The problem can also be extended to slack due-windows assignment and general position-dependent processing times. It is proved that both these extensions remain polynomially solvable.
References:
| [1] | Ahmadizar, F.; Farhadi, S., Single-Machine Batch Delivery Scheduling with Job Release Dates, Due Windows and Earliness, Tardiness, Holding and Delivery Costs, Computers & Operations Research, 53, 194-205 (2015) · Zbl 1348.90234 |
| [2] | Biskup, D., Single-Machine Scheduling with Learning Considerations, European Journal of Operational Research, 115, 1, 173-178 (1999) · Zbl 0946.90025 |
| [3] | Brucker, P., Scheduling Algorithms (2001), Berlin: Springer, Berlin · Zbl 1051.90011 |
| [4] | Feng, H., Tan, C., Xia, T., Pan, E., and Xi, L.. 2018. “Joint Optimization of Preventive Maintenance and Flexible Flowshop Sequence-Dependent Group Scheduling Considering Multiple Setups.” Engineering Optimization. doi:10.1080/0305215X.2018.1540696. · Zbl 1523.90155 |
| [5] | Geng, X.-N., Wang, J.-B., and Bai, D.. 2018. “Common Due Date Assignment Scheduling for a No-Wait Flowshop with Convex Resource Allocation and Learning Effect.” Engineering Optimization. doi:10.1080/0305215X.2018.1521397. |
| [6] | Gerstl, E.; Mosheiov, G., Minmax Due-Date Assignment with a Time Window for Acceptable Lead-Times, Annals of Operations Research, 211, 1, 167-177 (2013) · Zbl 1286.90081 |
| [7] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G., Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 |
| [8] | Hall, N. G.; Posner, M. E., Earliness-Tardiness Scheduling Problems. I: Weighted Deviation of Completion Times about a Common Due Date, Operations Research, 39, 5, 836-846 (1991) · Zbl 0749.90041 |
| [9] | Hardy, G. H.; Littlewood, J. E.; Pólya, G., Inequalities (1967), Cambridge, UK: Cambridge University Press, Cambridge, UK |
| [10] | Janiak, A.; Janiak, W. A.; Krysiak, T.; Kwiatkowski, T., A Survey on Scheduling Problems with Due Windows, European Journal of Operational Research, 242, 2, 347-357 (2015) · Zbl 1341.90002 |
| [11] | Ji, M.; Chen, K.; Ge, J.; Cheng, T. C. E., Group Scheduling and Job-Dependent Due Window Assignment Based on a Common Flow Allowance, Computers & Industrial Engineering, 68, 35-41 (2014) |
| [12] | Lee, W.-C.; Chung, Y.-H.; Wang, J.-Y., A Parallel-Machine Scheduling Problem with Two Competing Agents, Engineering Optimization, 49, 6, 962-975 (2017) |
| [13] | Li, G.; Luo, M.-L.; Zhang, W.-J.; Wang, X.-Y., Single-Machine Due-Window Assignment Scheduling Based on Common Flow Allowance, Learning Effect and Resource Allocation, International Journal of Production Research, 53, 4, 1228-1241 (2015) |
| [14] | Liman, S. D.; Panwalkar, S. S.; Thongmee, S., Determination of Common Due Window Location in a Single Machine Scheduling Problem, European Journal of Operational Research, 93, 1, 68-74 (1996) · Zbl 0912.90176 |
| [15] | Liman, S. D.; Panwalkar, S. S.; Thongmee, S., Common Due Window Size and Location Determination in a Single Machine Scheduling Problem, Journal of the Operational Research Society, 49, 9, 1007-1010 (1998) · Zbl 1140.90405 |
| [16] | Liu, W.; Hu, X.; Wang, X.-Y., Single Machine Scheduling with Slack Due Dates Assignment, Engineering Optimization, 49, 4, 709-717 (2017) |
| [17] | Liu, J.; Wang, Y.; Min, X., Single-Machine Scheduling with Common Due-Window Assignment for Deteriorating Jobs, Journal of the Operational Research Society, 65, 2, 291-301 (2014) |
| [18] | Liu, L.; Wang, J.-J.; Wang, X.-Y., Single Machine Due-Window Assignment Scheduling with Resource-Dependent Processing Times to Minimise Total Resource Consumption Cost, International Journal of Production Research, 54, 4, 1186-1195 (2016) |
| [19] | Mor, B.; Mosheiov, G., Scheduling a Maintenance Activity and Due-Window Assignment Based on Common Flow Allowance, International Journal of Production Economics, 135, 1, 222-230 (2012) |
| [20] | Mor, B.; Mosheiov, G., Scheduling a Deteriorating Maintenance Activity and Due-Window Assignment, Computers & Operations Research, 57, 33-40 (2015) · Zbl 1348.90292 |
| [21] | Mor, B.; Mosheiov, G., Minsum and Minmax Scheduling on a Proportionate Flowshop with Common Flow-Allowance, European Journal of Operational Research, 254, 2, 360-370 (2017) · Zbl 1346.90374 |
| [22] | Mosheiov, G.; Oron, D., Job-Dependent Due-Window Assignment Based on a Common Flow Allowance, Foundations of Computing and Decision Sciences, 35, 185-195 (2010) · Zbl 1204.90045 |
| [23] | Mosheiov, G.; Sarig, A., Minmax Scheduling Problems with a Common Due-Window, Computers & Operations Research, 36, 1886-1892 (2009) · Zbl 1179.90145 |
| [24] | Mosheiov, G.; Sidney, J. B., Scheduling with General Job-Dependent Learning Curves, European Journal of Operational Research, 147, 3, 665-670 (2003) · Zbl 1037.90529 |
| [25] | Nagano, M. S.; Rossi, F. L.; Martarelli, N. F., High-Performing Heuristics to Minimize Flowtime in No-Idle Permutation Flowshop, Engineering Optimization, 51, 2, 185-198 (2019) |
| [26] | Sun, L.-H., Ge, C.-C., Zhang, W., Wang, J.-B., and Lu, Y.-Y.. 2018. “Permutation Flowshop Scheduling with Simple Linear Deterioration.” Engineering Optimization. doi:10.1080/0305215X.2018.1519558. · Zbl 1523.90203 |
| [27] | Wang, J.-B.; Liu, L.; Wang, C., Single Machine SLK/DIF Due Window Assignment Problem with Learning Effect and Deteriorating Jobs, Applied Mathematical Modelling, 37, 18-19, 8394-8400 (2013) · Zbl 1426.90143 |
| [28] | Wang, J.-B.; Wang, C., Single-Machine Due-Window Assignment Problem with Learning Effect and Deteriorating Jobs, Applied Mathematical Modelling, 35, 8, 4017-4022 (2011) · Zbl 1221.90050 |
| [29] | Wang, J.-B.; Wang, M.-Z., Single-Machine Due-Window Assignment and Scheduling with Learning Effect and Resource-Dependent Processing Times, Asia-Pacific Journal of Operational Research, 31, 5 (2014) · Zbl 1299.90167 |
| [30] | Wang, J.-B.; Wang, M.-Z.; Ji, P., Scheduling Jobs with Processing Times Dependent on Position, Starting Time and Allotted Resource, Asia-Pacific Journal of Operational Research, 29, 5 (2012) · Zbl 1251.90198 |
| [31] | Wang, X.-R.; Wang, J.-B.; Jin, J.; Ji, P., Single Machine Scheduling with Truncated Job-Dependent Learning Effect, Optimization Letters, 8, 2, 669-677 (2014) · Zbl 1288.90037 |
| [32] | Wang, D.; Yin, Y.; Cheng, T. C. E., A Bicriterion Approach to Common Flow Allowances Due Window Assignment and Scheduling with Controllable Processing Times, Naval Research Logistics, 64, 1, 41-63 (2017) · Zbl 1411.90162 |
| [33] | Wu, Y.-B.; Wan, L.; Wang, X.-Y., Study on Due-Window Assignment Scheduling Based on Common Flow Allowance, International Journal of Production Economics, 165, 155-157 (2015) |
| [34] | Yang, D.-L.; Lai, C.-J.; Yang, S.-J., Scheduling Problems with Multiple Common Due Windows Assignment and Controllable Processing Times on a Single Machine, International Journal of Production Economics, 150, 96-103 (2014) |
| [35] | Yang, S.-W.; Wan, L.; Yin, N., Research on Single Machine SLK/DIF Due Window Assignment Problem with Learning Effect and Deteriorating Jobs, Applied Mathematical Modelling, 39, 15, 4593-4598 (2015) · Zbl 1443.90198 |
| [36] | Yeung, W.-K.; Oguz, C.; Cheng, T. C. E., Minimizing Weighted Number of Early and Tardy Jobs with a Common Due Window Involving Location Penalty, Annals of Operations Research, 108, 1-4, 33-54 (2001) · Zbl 0993.90044 |
| [37] | Yeung, W.-K.; Oguz, C.; Cheng, T. C. E., Single-Machine Scheduling with a Common Due Window, Computers & Operations Research, 28, 2, 157-175 (2001) · Zbl 0990.90050 |
| [38] | Yin, Y.; Cheng, T. C. E.; Hsu, C.-J.; Wu, C.-C., Single-Machine Batch Delivery Scheduling with an Assignable Common Due Window, Omega, 41, 2, 216-225 (2013) |
| [39] | Yin, Y.; Cheng, T. C. E.; Wang, J.; Wu, C.-C., Single-Machine Common Due Window Assignment and Scheduling to Minimize the Total Cost, Discrete Optimization, 10, 1, 42-53 (2013) · Zbl 1258.90046 |
| [40] | Yin, Y.; Cheng, T. C. E.; Wu, C.-C.; Cheng, S.-R., Single-Machine Due Window Assignment and Scheduling with a Common Flow Allowance and Controllable Job Processing Time, Journal of the Operational Research Society, 65, 1, 1-13 (2013) |
| [41] | Yin, Y.; Wang, D.; Cheng, T. C. E.; Wu, C.-C., Bi-Criterion Single-Machine Scheduling and Due Window Assignment with Common Flow Allowances and Resource Allocation, Journal of the Operational Research Society, 67, 9, 1169-1183 (2016) |
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.
