×

Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration. (English) Zbl 1230.90104

Summary: We address a two-machine flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes total weighted completion time. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational analysis on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm.

MSC:

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

References:

[1] Alidaee, B.; Womer, N. K., Scheduling with time dependent processing processing times: review and extensions, Journal of the Operational Research Society, 50, 711-720 (1999) · Zbl 1054.90542
[2] 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-13 (2004) · Zbl 1030.90023
[3] Gawiejnowicz, S., Time-Dependent Scheduling (2008), Springer: Springer Berlin · Zbl 1155.90004
[4] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations Research, 38, 495-498 (1990) · Zbl 0703.90051
[5] Cheng, T. C.E.; Ding, Q., The complexity of scheduling starting time dependent task with release dates, Information Processing Letters, 65, 75-79 (1998) · Zbl 1338.68096
[6] Ho, K. I.-J.; Leung, J. Y.-T.; Wei, W.-D., Complexity of scheduling tasks with time-dependent execution times, Information Processing Letters, 48, 315-320 (1993) · Zbl 0942.68508
[7] Mosheiov, G., V-shaped policies for scheduling deteriorating jobs, Operations Research, 39, 979-991 (1991) · Zbl 0748.90033
[8] Mosheiov, G., Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21, 653-659 (1994) · Zbl 0810.90074
[9] Sundararaghavan, P. S.; Kunnathur, A. S., Single machine scheduling with start time dependent processing times: some solvable cases, European Journal of Operational Research, 78, 394-403 (1994) · Zbl 0816.90088
[10] Wang, J.-B.; Xia, Z.-Q., Scheduling jobs under decreasing linear deterioration, Information Processing Letters, 94, 63-69 (2005) · Zbl 1182.68359
[11] Cheng, T. C.E.; Kang, L. Y.; Ng, C. T., Due-date assignment and parallel-machine scheduling with deteriorating jobs, Journal of the Operational Research Society, 58, 1103-1108 (2007) · Zbl 1278.90145
[12] Kang, L.; Ng, C. T., A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs, International Journal of Production Economics, 109, 180-184 (2007)
[13] Wu, C.-C.; Shiau, Y.-R.; Lee, W.-C., Single-machine group scheduling problems with deterioration consideration, Computers and Operations Research, 35, 1652-1659 (2008) · Zbl 1211.90094
[14] Wang, J.-B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Applied Mathematical Modelling, 34, 309-313 (2010) · Zbl 1185.90099
[15] Cheng, T. C.E.; Lee, W-C; Wu, C.-C., Scheduling problems with deteriorating jobs and learning effects including proportional setup times, Computers and Industrial Engineering, 58, 326-331 (2010)
[16] Gawiejnowicz, S.; Lin, B. M.T., Scheduling time-dependent jobs under mixed deterioration, Applied Mathematics and Computation, 216, 438-447 (2010) · Zbl 1188.90095
[17] Yang, S.-J., Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration, Applied Mathematics and Computation, 217, 3321-3329 (2010) · Zbl 1202.90149
[18] Chen, Z.-L., Parallel machine scheduling with time dependent processing times, Discrete Applied Mathematics, 70, 81-94 (1996) · Zbl 0855.68032
[19] Mosheiov, G., Multi-machine scheduling with linear deterioration, INFOR, 36, 205-214 (1998) · Zbl 07677568
[20] Ji, M.; Cheng, T. C.E., Parallel-machine scheduling with simple linear deterioration to minimize total completion time, European Journal of Operational Research, 188, 342-347 (2008) · Zbl 1149.90343
[21] Kuo, W.-H.; Yang, D-L, Parallel-machine scheduling with time dependent processing times, Theoretical Computer Science, 393, 204-210 (2008) · Zbl 1136.68015
[22] Huang, X.; Wang, M.-Z., Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties, Applied Mathematical Modelling, 35, 1349-1353 (2011) · Zbl 1211.90085
[23] Mosheiov, G., Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics, 117, 195-209 (2002) · Zbl 1004.68031
[24] Wang, J.-B.; Xia, Z.-Q., Flow shop scheduling with deteriorating jobs under dominating machines, Omega, 34, 327-336 (2006) · Zbl 1090.90095
[25] Wang, J.-B.; Ng, C. T.; Cheng, T. C.E.; Liu, L.-L., Minimizing total completion time in a two-machine flow shop with deteriorating jobs, Applied Mathematics and Computation, 180, 185-193 (2006) · Zbl 1104.90023
[26] 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, Computers and Operations Research, 37, 83-90 (2010) · Zbl 1171.90404
[27] Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117-129 (1976) · Zbl 0396.90041
[28] Ignall, E.; Schrage, L. E., Application of the branch and bound technique to some flowshop scheduling problems, Operations Research, 13, 400-412 (1965)
[29] Ho, J. C.; Gupta, J. N.D., Flowshop scheduling with dominant machines, Computers and Operations Research, 22, 237-246 (1995) · Zbl 0826.90064
[30] Croce, F. D.; Ghirardi, M.; Tadei, R., The two-machine total completion time flow shop problem, European Journal of Operational Research, 90, 227-237 (1996) · Zbl 0916.90148
[31] Wang, C.; Chu, C.; Proth, J. M., Efficient heuristic and optimal approaches for \(n / 2 / F / \sum C_i\) scheduling problems, International Journal of Production Economics, 44, 225-237 (1996)
[32] Hoogeveen, H.; Kawaguchi, T., Minimizing total completion time in a two-machine flowshop: analysis of special cases, Mathematics of Operations Research, 24, 887-913 (1999) · Zbl 0977.90015
[33] Croce, F. D.; Ghirardi, M.; Tadei, R., An improved branch-and-bound algorithm for the two machine total completion time flow shop problem, European Journal of Operational Research, 139, 293-301 (2002) · Zbl 1001.90065
[34] Chung, C. S.; Flynn, J.; Kirca, O., A branch and bound algorithm to minimize the total flow time for \(m\)-machine permutation flowshop problems, International Journal of Production Economics, 79, 185-196 (2002)
[35] Pinedo, M., Scheduling: Theory, Algorithms and Systems (2002), Prentice-Hall: Prentice-Hall New Jersey · Zbl 1145.90394
[36] Lee, W.-C.; Wu, C.-C., Minimizing total completion time in a two-machine flowshop with a learning effect, International Journal of Production Economics, 88, 85-93 (2004)
[37] Wang, J.-B.; Shan, F.; Jiang, B.; Wang, L.-Y., Permutation ow shop scheduling with dominant machines to minimize discounted total weighted completion time, Applied Mathematics and Computation, 62, 947-954 (2006) · Zbl 1116.90049
[38] Cheng, M.; Sun, S.; Yu, Y., A note on flow shop scheduling problems with a learning effect on no-idle dominant machines, Applied Mathematics and Computation, 184, 945-949 (2007) · Zbl 1143.90011
[39] Wang, J. B., Erratum to: A note on flow shop scheduling problems with a learning effect on no-idle dominant machines, Applied Mathematics and Computation, 202, 897-898 (2008) · Zbl 1144.90401
[40] Easwaran, G.; Parten, L. E.; Moras, R.; Uhlig, P. X., Makespan minimization in machine dominated flowshop, Applied Mathematics and Computation, 217, 110-116 (2010) · Zbl 1230.90088
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.