Single-machine due-window assignment problem with learning effect and deteriorating jobs. (English) Zbl 1221.90050
Summary: In this paper we consider a single-machine common due-window assignment scheduling problem with learning effect and deteriorating jobs. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The window location and size, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the window location, window size, earliness and tardiness. We show that the problem remains polynomially solvable under the proposed model.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Pinedo, M., Scheduling Theory, Algorithms, and Systems (2002), Prentice Hall: Prentice Hall New Jersey · Zbl 1145.90394 |
| [2] | Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Oper. Res., 38, 495-498 (1990) · Zbl 0703.90051 |
| [3] | Alidaee, B.; Womer, N. K., Scheduling with time dependent processing processing times: review and extensions, J. Oper. Res. Soc., 50, 711-720 (1999) · Zbl 1054.90542 |
| [4] | Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, Eur. J. Oper. Res., 152, 1-13 (2004) · Zbl 1030.90023 |
| [5] | Cheng, T. C.E.; Kang, L.; Ng, C. T., Due-date assignment and single machine scheduling with deteriorating jobs, J. Oper. Res. Soc., 55, 198-203 (2004) · Zbl 1095.90036 |
| [6] | Cheng, T. C.E.; Kang, L.; Ng, C. T., Single machine due-date scheduling of jobs with decreasing start-time dependent processing times, Int. Trans. Oper. Res., 12, 355-366 (2005) · Zbl 1131.90355 |
| [7] | Kuo, W. H.; Yang, D. L., A note on due-date assignment and single-machine scheduling with deteriorating jobs, J. Oper. Res. Soc., 59, 857-859 (2008) · Zbl 1153.90427 |
| [8] | Gawiejnowicz, S., Time-dependent Scheduling (2008), Springer: Springer Berlin · Zbl 1155.90004 |
| [9] | Yang, S.-J., Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration, Appl. Math. Comput., 217, 3321-3329 (2011) · Zbl 1202.90149 |
| [10] | Yang, S.-H.; Wang, J.-B., Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration, Appl. Math. Comput., 217, 4819-4826 (2011) · Zbl 1230.90104 |
| [11] | Huang, X.; Wang, M.-Z., Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties, Appl. Math. Model., 35, 1349-1353 (2011) · Zbl 1211.90085 |
| [12] | Wang, J.-B.; Wang, M.-Z., Single-machine scheduling with nonlinear deterioration, Optimiz. Lett. (2010) |
| [13] | Wang, J.-B.; Wang, J. J.; Ji, P., Scheduling jobs with chain precedence constraints and deteriorating jobs, J. Oper. Res. Soc. (2010) |
| [14] | Biskup, D., Single-machine scheduling with learning considerations, Eur. J. Oper. Res., 115, 173-178 (1999) · Zbl 0946.90025 |
| [15] | Cheng, T. C.E.; Wang, G., Single machine scheduling with learning effect considerations, Ann. Oper. Res., 98, 273-290 (2000) · Zbl 0967.68019 |
| [16] | Mosheiov, G., Scheduling problems with a learning effect, Eur. J. Oper. Res., 132, 687-693 (2001) · Zbl 1017.90051 |
| [17] | Eren, T.; Guner, E., A bicriteria scheduling with a learning effect: total completion time and total tardiness, INFOR: Inform. Syst. Oper. Res., 45, 75-81 (2007) · Zbl 07683663 |
| [18] | Eren, T.; Guner, E., Minimizing total tardiness in a scheduling problem with a learning effect, Appl. Math. Model., 31, 1351-1361 (2007) · Zbl 1145.90021 |
| [19] | Eren, T., A bicriteria parallel machine scheduling with a learning effect of setup and removal times, Appl. Math. Model., 33, 1141-1150 (2009) · Zbl 1168.90436 |
| [20] | Mosheiov, G.; Sarig, A., A due-window assignment problem with position-dependent processing times, J. Oper. Res. Soc., 59, 997-1003 (2008) · Zbl 1144.90391 |
| [21] | Gordon, V. S.; Potts, C. N.; Strusevich, V. A.; Whitehead, J. D., Single machine models with processing time deterioration: Handling precedence constraints via priority generation, J. Schedul., 11, 357-370 (2008) · Zbl 1168.90441 |
| [22] | Gordon, V. S.; Strusevich, V. A., Single machine scheduling and due date assignment with positionally dependent processing times, Eur. J. Oper. Res., 198, 57-62 (2009) · Zbl 1163.90781 |
| [23] | Lee, W. C.; Wu, C. C., A note on single-machine group scheduling problems with position-based learning effect, Appl. Math. Model., 33, 2159-2163 (2009) · Zbl 1205.90128 |
| [24] | Wu, C. C.; Lee, W. C., Single-machine and flowshop scheduling with a general learning effect model, Comput. Ind. Eng., 56, 1553-1558 (2009) |
| [25] | Biskup, D., A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 118, 315-329 (2008) · Zbl 1129.90022 |
| [26] | Lee, W-C., A note on deteriorating jobs and learning in single-machine scheduling problems, Int. J. Bus. Econ., 3, 83-89 (2004) |
| [27] | Wang, J-B., A note on scheduling problems with learning effect and deteriorating jobs, Int. J. Syst. Sci., 37, 827-833 (2006) · Zbl 1126.90347 |
| [28] | Wang, J. B., Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35, 397-402 (2007) |
| [29] | Wang, J. B.; Cheng, T. C.E., Scheduling problems with the effects of deterioration and learning, Asia-Pacific J. Oper. Res., 24, 245-261 (2007) · Zbl 1121.90066 |
| [30] | Wang, X.; Cheng, T. C.E., Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan, Eur. J. Oper. Res., 178, 57-70 (2007) · Zbl 1110.90045 |
| [31] | Cheng, T. C.E.; Wu, C. C.; Lee, W. C., Scheduling problems with deteriorating jobs and learning effects including proportional setup times, Comput. Ind. Eng., 58, 326-331 (2010) |
| [32] | Wang, J. B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Appl. Math. Model., 34, 309-313 (2010) · Zbl 1185.90099 |
| [33] | Nembhard, D. A.; Osothsilp, N., Task complexity effects on between-individual learning/forgetting variability, Int. J. Ind. Ergon., 29, 297-306 (2002) |
| [34] | Panwalker, S. S.; Smith, M. L.; Seidmann, A., Common due-date assignment to minimize total penalty for the one machine scheduling problem, Oper. Res., 30, 391-399 (1982) · Zbl 0481.90042 |
| [35] | Baker, K. R.; Scudder, G. D., Sequencing with earliness and tardiness penalties: a review, Oper. Res., 38, 22-36 (1990) · Zbl 0699.90052 |
| [36] | Kramer, F. J.; Lee, C. Y., Common due window scheduling, Prod. Oper. Manage., 2, 262-275 (1993) |
| [37] | Weng, M. X.; Ventura, J. A., Scheduling about a large common due-date with tolerance to minimized mean absolute deviation of completion times, Naval Res. Log., 41, 843-851 (1994) · Zbl 0827.90080 |
| [38] | Weng, M. X.; Ventura, J. A., A note on ‘Common due-window scheduling’, Prod. Oper. Manage., 5, 194-200 (1996) |
| [39] | Liman, S. D.; Panwalkar, S. S.; Thongmee, S., Determination of common due window location in a single machine scheduling problem, Eur. J. Oper. Res., 93, 68-74 (1996) · Zbl 0912.90176 |
| [40] | Liman, S. D.; Panwalkar, S. S.; Thongmee, S., Common due window size and location determination in a single machine scheduling problem, J. Oper. Res. Soc., 49, 1007-1010 (1998) · Zbl 1140.90405 |
| [41] | Gordon, V. S.; Proth, J. M.; Chu, C. B., A survey of the state of-the-art of common due date assignment and scheduling research, Eur. J. Oper. Res., 139, 1-25 (2002) · Zbl 1009.90054 |
| [42] | Gordon, V. S.; Proth, J. M.; Chu, C. B., Due date assignment and scheduling: SLK, TWK and other due date assignment models, Prod. Plan. Control, 13, 117-132 (2002) |
| [43] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044 |
| [44] | Hardy, G. H.; Littlewood, J. E.; Polya, G., Inequalities (1967), Cambridge University Press · Zbl 0634.26008 |
| [45] | Smith, W. E., Various optimizers for single-stage production, Naval Res. Log., 3, 59-66 (1956) |
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.
