# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
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 Scheduling theory, deterministic
##### 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 · doi:10.1016/S0377-2217(02)00909-8 [3] Gawiejnowicz, S.: Time-dependent scheduling, (2008) [4] Browne, S.; Yechiali, U.: Scheduling deteriorating jobs on a single processor, Operations research 38, 495-498 (1990) · Zbl 0703.90051 · doi:10.1287/opre.38.3.495 [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) [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 · doi:10.1016/0020-0190(93)90175-9 [7] Mosheiov, G.: V-shaped policies for scheduling deteriorating jobs, Operations research 39, 979-991 (1991) · Zbl 0748.90033 · doi:10.1287/opre.39.6.979 [8] Mosheiov, G.: Scheduling jobs under simple linear deterioration, Computers and operations research 21, 653-659 (1994) · Zbl 0810.90074 · doi:10.1016/0305-0548(94)90080-9 [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 · doi:10.1016/0377-2217(94)90048-5 [10] Wang, J. -B.; Xia, Z. -Q.: Scheduling jobs under decreasing linear deterioration, Information processing letters 94, 63-69 (2005) · Zbl 1182.68359 · doi:10.1016/j.ipl.2004.12.018 [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) [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 · doi:10.1016/j.cor.2006.09.008 [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 · doi:10.1016/j.apm.2009.04.020 [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 · doi:10.1016/j.amc.2010.01.037 [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 · doi:10.1016/j.amc.2010.08.064 [18] Chen, Z. -L.: Parallel machine scheduling with time dependent processing times, Discrete applied mathematics 70, 81-94 (1996) · Zbl 0855.68032 · doi:10.1016/0166-218X(96)00102-3 [19] Mosheiov, G.: Multi-machine scheduling with linear deterioration, Infor 36, 205-214 (1998) [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 · doi:10.1016/j.ejor.2007.04.050 [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 · doi:10.1016/j.tcs.2007.12.004 [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 · doi:10.1016/j.apm.2010.09.013 [23] Mosheiov, G.: Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete applied mathematics 117, 195-209 (2002) · Zbl 1004.68031 · doi:10.1016/S0166-218X(00)00385-1 · doi:http://www.elsevier.com/gej-ng/10/16/23/128/27/41/abstract.html [24] Wang, J. -B.; Xia, Z. -Q.: Flow shop scheduling with deteriorating jobs under dominating machines, Omega 34, 327-336 (2006) [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 · doi:10.1016/j.amc.2005.11.162 [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 · doi:10.1016/j.cor.2009.03.019 [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 · doi:10.1287/moor.1.2.117 [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 · doi:10.1016/0305-0548(94)E0007-T [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 · doi:10.1016/0377-2217(95)00351-7 [31] Wang, C.; Chu, C.; Proth, J. M.: Efficient heuristic and optimal approaches for $n/2/F/\sum$Ci 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 · doi:10.1287/moor.24.4.887 [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 · doi:10.1016/S0377-2217(01)00374-5 [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) [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 · doi:10.1016/j.amc.2006.04.052 [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 · doi:10.1016/j.amc.2006.05.206 [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 · doi:10.1016/j.amc.2007.10.049 [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 · doi:10.1016/j.amc.2010.05.022