×

Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects. (English) Zbl 1211.90084

Summary: We study an unrelated parallel machine scheduling problem with setup time and learning effects simultaneously. The setup time is proportional to the length of the already processed jobs. That is, the setup time of each job is past-sequence-dependent. The objective is to minimize the total completion time. We show that there exists a polynomial time solution for the proposed problem. We also discuss two special cases of the problem and show that they can be optimally solved by lower order algorithms.

MSC:

90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Cheng, T.C.E.; Wu, C.-C.; Lee, W.-C., Some scheduling problems with deteriorating jobs and learning effects, Comput. ind. eng., 54, 972-982, (2008)
[2] Yin, Y.; Xu, D.; Wang, J., Some single-machine scheduling problems with past-sequence-dependent setup times and a general learning effect, Int. J. adv. manufact. technol., 48, 1123-1132, (2010)
[3] Biskup, D., Single-machine scheduling with learning considerations, Eur. J. oper. res., 115, 173-178, (1999) · Zbl 0946.90025
[4] Mosheiov, G., Scheduling problems with learning effect, Eur. J. oper. res., 132, 687-693, (2001) · Zbl 1017.90051
[5] Mosheiov, G.; Sidney, J.B., Scheduling with general job-dependent learning curves, Eur. J. oper. res., 147, 665-670, (2003) · Zbl 1037.90529
[6] Kuo, W.-H.; Yang, D.-L., Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect, Eur. J. oper. res., 174, 1184-1190, (2006) · Zbl 1103.90341
[7] Alidaee, B.; Womer, N.K., Scheduling with time dependent processing times: review and extensions, J. oper. res. soc., 50, 711-720, (1999) · Zbl 1054.90542
[8] 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
[9] Biskup, D., A state-of-the-art review on scheduling with learning effects, Eur. J. oper. res., 188, 315-329, (2008) · Zbl 1129.90022
[10] Allahverdi, A.; Gupta, J.N.D.; Aldowaisan, T., A review of scheduling research involving setup considerations, Omega, 27, 219-239, (1999)
[11] Koulamas, C.; Kyparisis, G.J., Single-machine scheduling with past-sequence-dependent setup times, Eur. J. oper. res., 187, 1045-1049, (2008) · Zbl 1137.90498
[12] Kuo, W.-H.; Yang, D.-L., Single machine scheduling with past-sequence-dependent setup times and learning effects, Inform. process. lett., 102, 22-26, (2007) · Zbl 1184.68132
[13] Biskup, D.; Herrmann, J., Single-machine scheduling against due dates with past-sequence-dependent setup times, Eur. J. oper. res., 191, 587-592, (2008) · Zbl 1147.90010
[14] Kanet, J.J., Minimizing variation of flow time in single machine systems, Manag. sci., 27, 1453-1459, (1981) · Zbl 0473.90048
[15] Wang, J.-B., Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect, Comput. ind. eng., 55, 584-591, (2008)
[16] Wang, J.-B.; Wang, D.; Wang, L.Y.; Lin, L.; Yin, N.; Wang, W.W., Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times, Comput. math. appl., 57, 9-16, (2009) · Zbl 1165.90471
[17] Wang, J.-B.; Jiang, Y.; Wang, G., Single-machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning, Int. J. adv. manufact. technol., 41, 1221-1226, (2009)
[18] Wang, X.-R.; Wang, J.-B.; Gao, W.-J.; Huang, X., Scheduling with past-sequence-dependent setup times and learning effects on a single machine, Int. J. adv. manufact. technol., 48, 739-746, (2010)
[19] Yin, N.; Wang, J.-B.; Wang, D.; Wang, L.-Y.; Wang, X.-Y., Deteriorating jobs and learning effects on a single-machine scheduling with past-sequence-dependent setup times, Int. J. adv. manufact. technol., 46, 707-714, (2010)
[20] C. Zhao, H. Tang, Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs, Comput. Ind. Eng. in press, doi:10.1016/j.cie.2010.07.015.
[21] 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
[22] Mosheiov, G., Parallel-machine scheduling with a learning effect, J. oper. res. soc., 52, 1165-1169, (2001) · Zbl 1178.90159
[23] Hardy, G.H.; Littlewood, J.E.; Polya, G., Inequalities, (1967), Cambridge University Press London · Zbl 0634.26008
[24] Kuo, W.-H.; Yang, D.-L., Parallel-machine scheduling with time dependent processing times, Theor. comput. sci., 393, 204-210, (2008) · Zbl 1136.68015
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.