×

Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times. (English) Zbl 1217.90103

Summary: In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier – this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gupta, J. N.D.; Gupta, S. K., Single facility scheduling with nonlinear processing times, Comput. Ind. Eng., 14, 387-393 (1988)
[2] Kunnathur, A. S.; Gupta, S. K., Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, Eur. J. Oper. Res., 47, 1, 56-64 (1990) · Zbl 0717.90034
[3] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Oper. Res., 38, 495-498 (1990) · Zbl 0703.90051
[4] 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
[5] 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
[6] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Pareto and scalar bicriterion optimization in scheduling deteriorating jobs, Comput. Oper. Res., 33, 746-767 (2006) · Zbl 1116.90045
[7] Ji, M.; He, Y.; Cheng, T. C.E., Scheduling linear deteriorating jobs with an availability constraint on a single machine, Theor. Comput. Sci., 362, 115-126 (2006) · Zbl 1100.68009
[8] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences, Discrete Appl. Math., 154, 2150-2166 (2006) · Zbl 1113.90059
[9] Wu, C. C.; Lee, W. C., Two-machine flowshop scheduling to minimize mean flow time under linear deterioration, Int. J. Prod. Econ., 103, 572-584 (2006)
[10] Shiau, Y. R.; Lee, W. C.; Wu, C. C.; Chang, C. M., Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration, Int. J. Adv. Manuf. Technol., 34, 774-782 (2007)
[11] Kang, L.; Ng, C. T., A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs, Int. J. Prod. Econ., 109, 180-184 (2007)
[12] Gawiejnowicz, S., Scheduling deteriorating jobs subject to job or machine availability constraints, Eur. J. Oper. Res., 180, 472-478 (2007) · Zbl 1114.90034
[13] Wu, C. C.; Lee, W. C.; Shiau, Y. R., Minimizing the total weighted completion time on a single machine under linear deterioration, Int. J. Adv. Manuf. Technol., 33, 1237-1243 (2007)
[14] Raut, S.; Swami, S.; Gupta, J. N.D., Scheduling a capacitated single machine with time deteriorating job values, Int. J. Prod. Econ., 114, 769-780 (2008) · Zbl 1167.90516
[15] Lee, W. C.; Wu, C. C.; Chung, Y. H., Scheduling deteriorating jobs on a single machine with release times, Comput. Ind. Eng., 54, 441-452 (2008)
[16] Lee, W. C.; Wu, C. C.; Chung, Y. H.; Liu, H. C., Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates, Comput. Oper. Res., 36, 2111-2121 (2009) · Zbl 1179.90142
[17] Biskup, D.; Herrmann, J., Single-machine scheduling against due dates with past-sequence-dependent setup times, Eur. J. Oper. Res., 191, 2, 587-592 (2008) · Zbl 1147.90010
[18] 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
[19] Ng, C. T.; Wang, J.-B.; Cheng, T. C.E.; Liu, L. L., A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs, Comput. Oper. Res., 37, 1, 83-90 (2010) · Zbl 1171.90404
[20] Cheng, T. C.E.; Gupta, J. N.D.; Wang, G., A review of flowshop scheduling research with setup times, Prod. Oper. Manage., 9, 3, 262-282 (2000)
[21] Allahverdi, A.; Gupta, J. N.D.; Aldowaisan, T., A review of scheduling research involving setup considerations, Omega, 27, 219-239 (1999)
[22] Allahverdi, A.; Ng, C. T.; Cheng, T. C.E.; Kovalyov, M. Y., A survey of scheduling problems with setup times or costs, Eur. J. Oper. Res., 187, 3, 985-1032 (2008) · Zbl 1137.90474
[23] 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
[24] Wu, C. C.; Shiau, Y. R.; Lee, W. C., Single-machine group scheduling problems with deterioration consideration, Comput. Oper. Res., 35, 1652-1659 (2008) · Zbl 1211.90094
[25] Wu, C. C.; Lee, W. C., Single-machine group-scheduling problems with deteriorating setup times and job-processing times, Int. J. Prod. Econ., 115, 128-133 (2008)
[26] Lee, W. C.; Wu, C. C., Multi-machine scheduling with deteriorating jobs and scheduled maintenance, Appl. Math. Model., 32, 362-373 (2008) · Zbl 1187.90134
[27] Allahverdi, A.; Soroush, H. M., The significance of reducing setup times/setup costs, Eur. J. Oper. Res., 187, 978-984 (2008) · Zbl 1137.90475
[28] 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
[29] Wang, J.-B., Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect, Comput. Ind. Eng., 55, 3, 584-591 (2008)
[30] 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
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.