×
Gawiejnowicz, Stanisław

A review of four decades of time-dependent scheduling: main results, new topics, and open problems. (English) Zbl 1434.90057

J. Sched. 23, No. 1, 3-47 (2020).
Summary: This paper is a comprehensive review of the research conducted over the past four decades in the domain of time-dependent scheduling, where variable processing times of jobs depend on when the jobs start. The paper is divided into four parts. The first part recalls some definitions and notions, introduces terminology, and defines the main models of time-dependent job processing times and the notation that is used throughout the paper. The second part summarizes four decades of time-dependent scheduling research, focusing on the computational complexity of time-dependent scheduling problems, and algorithms solving these problems. The results are divided into groups with respect to the machine environment and illustrated by examples. The third part concentrates on new topics in time-dependent scheduling, such as two-agent time-dependent scheduling, mutually related time-dependent scheduling problems, and time-dependent scheduling games. The last part discusses the most important time-dependent scheduling problems which still await solution. The paper is completed by bibliographic notes and an extensive list of references.

Cited in 25 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Keywords:

scheduling; deteriorating jobs; shortening jobs; alterable jobs; single machine; parallel machines; dedicated machines; computational complexity; algorithms; approximation schemes
Cite Review PDF
Full Text: DOI

References:

[1] Achugbue, Jo; Chin, Fy, Scheduling the open shop to minimize mean flow time, SIAM Journal on Computing, 11, 709-720 (1982) · Zbl 0492.68038
[2] Agnetis, A.; Billaut, J-C; Gawiejnowicz, S.; Pacciarelli, D.; Soukhal, A., Multi-agent Scheduling: Models and Algorithms (2014), Berlin: Springer, Berlin · Zbl 1286.90002
[3] Agnetis, A.; Mirchandani, P.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Operations Research, 52, 229-242 (2004) · Zbl 1165.90446
[4] Albers, S.; Robert, Y.; Vivien, F., Online scheduling, Introduction to scheduling, 51-57 (2010), Boca Raton: Chapmann and Hall, Boca Raton
[5] Alidaee, B., A heuristic solution procedure to minimize makespan on a single machine with non-linear cost functions, Journal of the Operational Research Society, 41, 1065-1068 (1990) · Zbl 0738.90039
[6] Alidaee, B.; Womer, Nk, Scheduling with time dependent processing times: Review and extensions, Journal of the Operational Research Society, 50, 711-720 (1999) · Zbl 1054.90542
[7] Arigliano, A.; Ghiani, G.; Grieco, A.; Guerriero, E., Single-machine time-dependent scheduling problems with fixed rate-modifying activities and resumable jobs, 4OR-Q, Journal of Operations Research, 15, 201-215 (2017) · Zbl 1369.90070
[8] Bachman, A.; Janiak, A., Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126, 557-566 (2000) · Zbl 0976.90039
[9] Bachman, A.; Janiak, A.; Kovalyov, My, Minimizing the total weighted completion time of deteriorating jobs, Information Processing Letters, 81, 81-84 (2002) · Zbl 1032.68019
[10] Baker, K.; Smith, Jc, A multiple criterion model for machine scheduling, Journal of Scheduling, 6, 7-16 (2003) · Zbl 1154.90406
[11] Bampis, E., & Kononov, A. (2001). On the approximability of scheduling multiprocessor tasks with time-dependent processor and time requirements. In The 15th international symposium on parallel and distributed processing (pp. 2144-2151).
[12] Barketau, Ms; Cheng, T-Ce; Ng, Ct; Kotov, V.; Kovalyov, My, Batch scheduling of step deteriorating jobs, Journal of Scheduling, 11, 17-28 (2008) · Zbl 1168.90421
[13] Bartal Y., Leonardi S., Marchetti-Spaccamela A., Sgal J., & Stougie L. (1996). Multiprocessor scheduling with rejection. In The 7th symposium on discrete algorithms (pp. 95-103). · Zbl 0845.90068
[14] Blazewicz, J.; Ecker, K.; Pesch, E.; Schmidt, G.; Sterna, M.; Weglarz, J., Handbook on scheduling: from applications to theory (2019), Berlin: Springer, Berlin
[15] Blazewicz, J.; Ecker, K.; Pesch, E.; Schmidt, G.; Weglarz, J., Handbook on scheduling: from theory to applications (2007), Berlin: Springer, Berlin · Zbl 1165.90009
[16] Bosio, A.; Righini, G., A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times, Mathematical Methods of Operations Research, 69, 271-280 (2009) · Zbl 1167.90005
[17] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations Research, 38, 495-498 (1990) · Zbl 0703.90051
[18] Burkard, R.; Dell’Amico, M.; Martello, S., Assignment problems, revised reprint (2012), Philadelphia: SIAM, Philadelphia
[19] Cai, P.; Cai, J-Y; Naik, Av, Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns, Journal of Combinatorial Optimization, 1, 367-376 (1998) · Zbl 0896.90136
[20] Cai, J-Y; Cai, P.; Zhu, Y., On a scheduling problem of time deteriorating jobs, Journal of Complexity, 14, 190-209 (1998) · Zbl 0910.68019
[21] Chen, Z-L, A note on single-processor scheduling with time-dependent execution times, Operations Research Letters, 17, 127-129 (1995) · Zbl 0841.90072
[22] Chen, Zhi-Long, Parallel machine scheduling with time dependent processing times, Discrete Applied Mathematics, 70, 1, 81-93 (1996) · Zbl 0855.68032
[23] Cheng, T-Ce; Ding, Q., The complexity of scheduling starting time dependent tasks with release times, Information Processing Letters, 65, 75-79 (1998) · Zbl 1338.68096
[24] Cheng, T-Ce; Ding, Q., The time dependent makespan problem is strongly NP-complete, Computers and Operations Research, 26, 749-754 (1999) · Zbl 0932.90013
[25] Cheng, T-Ce; Ding, Q., Single machine scheduling with deadlines and increasing rates of processing times, Acta Informatica, 36, 673-692 (2000) · Zbl 0958.68018
[26] Cheng, T-Ce; Ding, Q., Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine, Computers and Operations Research, 30, 51-62 (2003) · Zbl 1029.90028
[27] Cheng, T-Ce; Ding, Q.; Lin, Bm-T, A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152, 1-13 (2004) · Zbl 1030.90023
[28] Cheng, T-Ce; He, Y.; Hoogeveen, H.; Ji, M.; Woeginger, G., Scheduling with step-improving processing times, Operations Research Letters, 34, 37-40 (2006) · Zbl 1080.90044
[29] Cheng, T-Ce; Shafransky, Y.; Ng, C-T, An alternative approach for proving the NP-hardness of optimization problems, European Journal of Operational Research, 248, 52-58 (2016) · Zbl 1346.90833
[30] Cheng, M-B; Sun, S-J, A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs, Journal of Shanghai University, 11, 451-456 (2007) · Zbl 1174.90461
[31] Cheng, Y-S; Sun, S-J, Scheduling linear deteriorating jobs with rejection on a single machine, European Journal of Operational Research, 194, 18-27 (2009) · Zbl 1179.90132
[32] Cheng, M-B; Sun, S-J; He, L-M, Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines, European Journal of Operational Research, 183, 115-124 (2007) · Zbl 1127.90024
[33] Cheng, M-B; Tadikamalla, Pr; Shang, J.; Zhang, B., Two-machine flow shop scheduling with deteriorating jobs: Minimizing the weighted sum of makespan and total completion time, Journal of the Operational Research Society, 66, 709-719 (2015)
[34] Cheng, M-B; Tadikamalla, Pr; Shang, J.; Zhang, S-Q, Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs, European Journal of Operational Research, 234, 650-657 (2014) · Zbl 1304.90091
[35] Cheng, M-B; Wang, G-Q; He, L-M, Parallel machine scheduling problems with proportionally deteriorating jobs, International Journal of Systems Science, 40, 53-57 (2009) · Zbl 1155.90376
[36] Chen, Q.; Lin, L.; Tan, Z.; Yan, Y., Coordination mechanisms for scheduling games with proportional deterioration, European Journal of Operational Research, 263, 380-389 (2017) · Zbl 1380.90109
[37] Chryssolouris, G., Manufacturing systems: Theory and practice (2006), Berlin: Springer, Berlin
[38] Conway, Rw; Maxwell, Wl; Miller, Lw, Theory of scheduling (1967), Reading: Addison-Wesley, Reading · Zbl 1058.90500
[39] Dȩbczyński, M., Maximum cost scheduling of jobs with mixed variable processing times and k-partite precedence constraints, Optimization Letters, 8, 395-400 (2014) · Zbl 1288.90115
[40] Dȩbczyński, M.; Gawiejnowicz, S., Scheduling jobs with mixed processing times, arbitrary precedence constraints and maximum cost criterion, Computers and Industrial Engineering, 64, 273-279 (2013)
[41] Dror, M.; Kubiak, W.; Dell’Olmo, P., Scheduling chains to minimize mean flow time, Information Processing Letters, 61, 297-301 (1997) · Zbl 1337.68128
[42] Du, J.; Leung, Jy-T, Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15, 483-495 (1990) · Zbl 0714.90052
[43] Fan, B.; Li, S.; Zhou, L.; Zhang, L., Scheduling resumable deteriorating jobs on a single machine with non-availability constraints, Theoretical Computer Science, 412, 275-280 (2011) · Zbl 1207.90054
[44] Fiat, A.; Woeginger, G., Online algorithms: The state of the art (1998), Berlin: Springer, Berlin · Zbl 1177.68009
[45] Fiszman, S.; Mosheiov, G., Minimizing total load on a proportionate flowshop with position-dependent processing times and rejection, Information Processing Letters, 132, 39-43 (2018) · Zbl 1410.90086
[46] Garey, Mr; Johnson, Ds, Computers and intractability: A guide to the theory of NP-completeness (1979), San Francisco: W. H. Freeman, San Francisco · Zbl 0411.68039
[47] Garey, Mr; Johnson, Ds; Sethi, R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117-129 (1976) · Zbl 0396.90041
[48] Gawiejnowicz, S., A note on scheduling on a single processor with speed dependent on a number of executed jobs, Information Processing Letters, 57, 297-300 (1996) · Zbl 0875.68080
[49] Gawiejnowicz, S., Brief survey of continuous models of scheduling, Foundations of Computing and Decision Sciences, 21, 81-100 (1996) · Zbl 0862.90078
[50] Gawiejnowicz, S., Scheduling jobs with varying processing times (1997), Poznań: Poznań University of Technology, Poznań
[51] Gawiejnowicz, S. (2005). Complexity of scheduling deteriorating jobs with machine or job availability constraints. In The 7th workshop on models and algorithms for planning and scheduling problems (pp. 140-141).
[52] Gawiejnowicz, S., Scheduling deteriorating jobs subject to job or machine availability constraints, European Journal of Operational Research, 180, 472-478 (2007) · Zbl 1114.90034
[53] Gawiejnowicz, S., Time-dependent scheduling (2008), Berlin: Springer, Berlin · Zbl 1155.90004
[54] Gawiejnowicz, S., Models and algorithms of time-dependent scheduling (2020), Berlin: Springer, Berlin · Zbl 1453.90002
[55] Gawiejnowicz, S.; Kononov, A., Complexity and approximability of scheduling resumable proportionally deteriorating jobs, European Journal of Operational Research, 200, 305-308 (2010) · Zbl 1183.90170
[56] Gawiejnowicz, S.; Kononov, A., Isomorphic scheduling problems, Annals of Operations Research, 213, 131-145 (2014) · Zbl 1296.90045
[57] Gawiejnowicz, S.; Kurc, W., Structural properties of time-dependent scheduling problems with the norm objective, Omega-International Journal of Management Science, 57, 196-202 (2015)
[58] Gawiejnowicz, S., & Kurc, W. (2017) A new necessary condition of optimality for a single machine scheduling problem with deteriorating jobs. In The 13th workshop on models and algorithms for planning and scheduling problems (pp. 177-179).
[59] Gawiejnowicz, S., & Kurc, W. (2018). Two matheuristics for problem \(1|p_j=1+b_jt|\sum C_j\). In The 2nd international workshop on dynamic scheduling problems (pp. 45-50).
[60] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., A greedy approach for a time-dependent scheduling problem, Lecture Notes in Computer Science, 2328, 79-86 (2002) · Zbl 1057.68547
[61] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Minimizing time-dependent total completion time on parallel identical machines, Lecture Notes in Computer Science, 3019, 89-96 (2004) · Zbl 1128.68333
[62] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences, Discrete Applied Mathematics, 154, 2150-2166 (2006) · Zbl 1113.90059
[63] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Parallel machine scheduling of deteriorating jobs by modified steepest descent search, Lecture Notes in Computer Science, 3911, 116-123 (2006) · Zbl 1182.90042
[64] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Pareto and scalar bicriterion scheduling of deteriorating jobs, Computers and Operations Research, 33, 746-767 (2006) · Zbl 1116.90045
[65] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Equivalent time-dependent scheduling problems, European Journal of Operational Research, 196, 919-929 (2009) · Zbl 1176.90213
[66] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Conjugate problems in time-dependent scheduling, Journal of Scheduling, 12, 543-553 (2009) · Zbl 1176.90212
[67] Gawiejnowicz, S.; Lai, T-C; Chiang, M-H, Scheduling linearly shortening jobs under precedence constraints, Applied Mathematical Modelling, 35, 2005-2015 (2011) · Zbl 1217.90104
[68] Gawiejnowicz, S.; Lee, W-C; Lin, C-L; Wu, C-C, Single-machine scheduling of proportionally deteriorating jobs by two agents, Journal of the Operational Research Society, 62, 1983-1991 (2011)
[69] Gawiejnowicz, S.; Lin, Bm-T, Scheduling time-dependent jobs under mixed deterioration, Applied Mathematics and Computation, 216, 438-447 (2010) · Zbl 1188.90095
[70] Gawiejnowicz, S.; Pankowska, L., Scheduling jobs with varying processing times, Information Processing Letters, 54, 175-178 (1995) · Zbl 0875.68421
[71] Gawiejnowicz, S.; Suwalski, C., Scheduling linearly deteriorating jobs by two agents to minimize the weighted sum of two criteria, Computers and Operations Research, 52, 135-146 (2014) · Zbl 1348.90261
[72] Gonzalez, T.; Sahni, S., Open shop scheduling to minimize finish time, Journal of ACM, 23, 665-679 (1976) · Zbl 0343.68031
[73] Gordon, Vs; Potts, Cn; Strusevich, Va; Whitehead, Jd, Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation, Journal of Scheduling, 11, 357-370 (2008) · Zbl 1168.90441
[74] Graham, Rl, Bounds for certain multiprocessing anomalies, Bell Labs Technical Journal, 45, 1563-1581 (1966) · Zbl 0168.40703
[75] Graham, Rl, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics, 17, 416-429 (1969) · Zbl 0188.23101
[76] Graham, Rl; Lawler, El; Lenstra, Jk; Rinnooy Kan, Ahg, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
[77] Gupta, Jnd; Gupta, Sk, Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14, 387-393 (1988)
[78] Gupta, Sk; Kunnathur, As; Dandapani, K., Optimal repayment policies for multiple loans, Omega-International Journal of Management Science, 15, 323-330 (1987)
[79] Halman, N. (2018). FPTASes for minimizing makespan of deteriorating jobs with non-linear processing times. In The 2nd international workshop on dynamic scheduling problems (pp. 51-56).
[80] Halman, N.; Klabjan, D.; Li, C-L; Orlin, J.; Simchi-Levi, D., Fully polynomial time approximation schemes for stochastic dynamic programs, SIAM Journal on Discrete Mathematics, 28, 1725-1796 (2014) · Zbl 1408.68078
[81] Halman, N.; Klabjan, D.; Mostagir, M.; Orlin, J.; Simchi-Levi, D., A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand, Mathematics of Operations Research, 34, 674-685 (2009) · Zbl 1231.90030
[82] Hardy, G.; Littlewood, Je; Polya, G., Inequalities (1934), London: Cambridge University Press, London · JFM 60.0169.01
[83] He, C.; Leung, Jy-T, Two-agent scheduling of deteriorating jobs, Journal of Combinatorial Optimization, 34, 362-367 (2017) · Zbl 1382.90035
[84] Ho, J.; Gupta, Jnd, Flowshop scheduling with dominant machines, Computers and Operations Research, 22, 237-246 (1995) · Zbl 0826.90064
[85] Ho, J.; Wong, J., Makespan minimization for m parallel identical processors, Naval Research Logistics, 42, 935-948 (1995) · Zbl 0841.90076
[86] Ho, Ki-J; Leung, Jy-T; Wei, W-D, Complexity of scheduling tasks with time-dependent execution times, Information Processing Letters, 48, 315-320 (1993) · Zbl 0942.68508
[87] Holloway, Ca; Nelson, Rt, Job shop scheduling with due dates and variable processing times, Management Science, 20, 1264-1275 (1974) · Zbl 0303.90027
[88] Hsieh, Y-C; Bricker, Dl, Scheduling linearly deteriorating jobs on multiple machines, Computers and Industrial Engineering, 32, 727-734 (1997)
[89] Jaehn, F.; Sedding, Ha, Scheduling with time-dependent discrepancy times, Journal of Scheduling, 19, 737-757 (2016) · Zbl 1386.90057
[90] Jafari, A-A; Khademi-Zare, H.; Lotfi, Mm; Tavakkoli-Moghaddam, R., A note on “On three-machine flow shop scheduling with deteriorating jobs”, International Journal of Production Economics, 191, 250-252 (2017)
[91] Ji, M.; Cheng, T-Ce, An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan, Information Processing Letters, 102, 41-47 (2007) · Zbl 1184.68125
[92] Ji, M.; Cheng, T-Ce, Parallel-machine scheduling with simple linear deterioration to minimize total completion time, European Journal of Operational Research, 188, 342-347 (2008) · Zbl 1149.90343
[93] Ji, M.; Cheng, T-Ce, Parallel-machine scheduling of simple linear deteriorating jobs, Theoretical Computer Science, 410, 3761-3768 (2009) · Zbl 1171.68003
[94] Ji, M.; Cheng, T-Ce, Scheduling resumable simple linear deteriorating jobs on a single machine with an availability constraint to minimize makespan, Computers and Industrial Engineering, 59, 794-798 (2010)
[95] Ji, M.; He, Y.; Cheng, T-Ce, Scheduling linear deteriorating jobs with an availability constraint on a single machine, Theoretical Computer Science, 362, 115-126 (2006) · Zbl 1100.68009
[96] Johnson, Sm, Optimal two and three stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[97] Johnson, Ds, The NP-completeness column: An ongoing guide, Journal of Algorithms, 2, 393-405 (1982) · Zbl 0494.68047
[98] Kacem, I.; Levner, E., An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs, Journal of Industrial and Management Optimization, 12, 811-817 (2016) · Zbl 1331.90027
[99] Kang, L-Y; Cheng, T-Ce; Ng, C-T; Zhao, M., Scheduling to minimize makespan with time-dependent processing times, Lecture Notes in Computer Science, 3827, 925-933 (2005) · Zbl 1175.90172
[100] Kang, L-Y; 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)
[101] Karp, Rm; Miller, Re; Thatcher, Jw, Reducibility among combinatorial problems, Complexity of computer computations, 85-103 (1972), New York: Plenum Press, New York · Zbl 1467.68065
[102] Kawase, Y.; Makino, K.; Seimi, K., Optimal composition ordering problems for piecewise linear functions, Algorithmica, 80, 2134-2159 (2018) · Zbl 1392.68204
[103] Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems (2004), Berlin: Springer, Berlin · Zbl 1103.90003
[104] Kelly, Fp, A remark on search and sequencing problems, Mathematics of Operations Research, 7, 154-157 (1982) · Zbl 0502.90049
[105] Klamroth, K.; Wiecek, M., A time-dependent multiple criteria single-machine scheduling problem, European Journal of Operational Research, 135, 17-26 (2001) · Zbl 1077.90529
[106] Kohler, Wh; Steiglitz, K.; Coffman, Eg Jr, Enumerative and iterative computational approaches, Computer and Job-Shop Scheduling Theory (1976), New York: Wiley, New York
[107] Kononov, A. (1999). On the complexity of the problems of scheduling with time-dependent job processing times, Ph.D. thesis, Sobolev Institute of Mathematics, Novosibirsk (in Russian).
[108] Kononov, A., Combinatorial complexity of scheduling jobs with simple linear deterioration, Discrete Analysis and Operations Research, 3, 15-32 (1996) · Zbl 0859.90086
[109] Kononov, A.; Zimmermann, U., Scheduling problems with linear increasing processing times, Operations research 1996, 208-212 (1997), Berlin: Springer, Berlin · Zbl 0918.90085
[110] Kononov, A., Single machine scheduling problems with processing times proportional to an arbitrary function, Discrete Analysis and Operations Research, 5, 17-37 (1998) · Zbl 0921.90086
[111] Kononov, A.; Gawiejnowicz, S., NP-hard cases in scheduling deteriorating jobs on dedicated machines, Journal of the Operational Research Society, 52, 708-718 (2001) · Zbl 1181.90120
[112] Korte, B.; Vygen, J., Combinatorial Optimization: Theory and Algorithms (2018), Berlin: Springer, Berlin · Zbl 1390.90001
[113] Koulamas, C., The single-machine total tardiness scheduling problem: Review and extensions, European Journal of Operational Research, 202, 1-7 (2010) · Zbl 1175.90174
[114] Koutsoupias, E.; Papadimitriou, C., Worst-case equilibria, Computer Science Review, 3, 65-69 (2009) · Zbl 1303.91012
[115] Kovalyov, My; Kubiak, W., A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3, 287-297 (1998) · Zbl 0903.90100
[116] Kubale, M.; Ocetkiewicz, K., A new optimal algorithm for a time-dependent scheduling problem, Control and Cybernets, 38, 713-721 (2009) · Zbl 1301.93064
[117] Kubiak, W.; Van De Velde, Sl, Scheduling deteriorating jobs to minimize makespan, Naval Research Logistics, 45, 511-523 (1998) · Zbl 0936.90026
[118] Kunnathur, As; Gupta, Sk, Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European Journal of Operational Research, 47, 56-64 (1990) · Zbl 0717.90034
[119] Kuo, W-H; Hsu, C-J; Yang, D-L, A note on unrelated parallel machine scheduling with time-dependent processing times, Journal of the Operational Research Society, 60, 431-434 (2009) · Zbl 1156.90366
[120] Kuo, W-H; Yang, D-L, Single-machine scheduling problems with start-time dependent processing time, Computers and Mathematics with Applications, 53, 1658-1664 (2007) · Zbl 1152.90450
[121] Kuo, W-H; Yang, D-L, Parallel-machine scheduling with time-dependent processing times, Theoretical Computer Science, 393, 204-210 (2008) · Zbl 1136.68015
[122] Kuo, W-H; Yang, D-L, Single-machine scheduling with deteriorating jobs, International Journal of Systems Science, 43, 132-139 (2012) · Zbl 1259.90036
[123] Lawler, El, Optimal sequencing of a single machine subject to precedence constraints, Management of Science, 19, 544-546 (1973) · Zbl 0254.90039
[124] Lawler, El, Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Annals of Discrete Mathematics, 2, 75-90 (1978) · Zbl 0374.68033
[125] Lawler, El; Woods, De, Branch-and-bound methods: A survey, Operations Research, 14, 699-719 (1966) · Zbl 0143.42501
[126] Lee, C-Y; Leon, Vj, Machine scheduling with a rate-modifying activity, European Journal of Operational Research, 128, 119-128 (2001) · Zbl 0983.90020
[127] Lee, W-C; Shiau, Y-R; Chen, S-K; Wu, C-C, A two-machine flowshop scheduling problem with deteriorating jobs and blocking, International Journal of Production Economics, 124, 188-197 (2010)
[128] Lee, W-C; Wang, W-J; Shiau, Y-R; Wu, C-C, A single-machine scheduling problem with two-agent and deteriorating jobs, Applied Mathematical Modelling, 34, 3098-3107 (2010) · Zbl 1201.90080
[129] Lee, W-C; Wu, C-C; Chung, Y-H, Scheduling deteriorating jobs on a single machine with release times, Computers and Industrial Engineering, 54, 441-452 (2008)
[130] Lee, W-C; Wu, C-C; Wen, C-C; Chung, Y-H, A two-machine flowshop makespan scheduling problem with deteriorating jobs, Computers and Industrial Engineering, 54, 737-749 (2008)
[131] Leung, Jy-T, Handbook of scheduling: Models, algorithms and performance analysis (2004), New York: Chappman & Hall, New York · Zbl 1103.90002
[132] Leung, Jy-T; Ng, C-T; Cheng, T-Ce, Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times, European Journal of Operational Research, 187, 1090-1099 (2008) · Zbl 1138.90396
[133] Li, S-S, Scheduling proportionally deteriorating jobs in two-machine open shop with a non-bottleneck machine, Asia-Pacific Journal of Operations Research, 28, 623-631 (2011) · Zbl 1228.90037
[134] Li, K.; Liu, C.; Li, K., An approximation algorithm based on game theory for scheduling simple linear deteriorating jobs, Theoretical Computer Science, 543, 46-51 (2014) · Zbl 1360.90128
[135] Li, S-S; Ng, C-T; Cheng, T-Ce; Yuan, J-J, Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan, European Journal of Operational Research, 210, 482-488 (2011) · Zbl 1213.90121
[136] Liu, P.; Tang, L., Two-agent scheduling with linear deteriorating jobs on a single machine, Lecture Notes in Computer Science, 5092, 642-650 (2008) · Zbl 1148.90324
[137] Liu, P.; Tang, L.; Zhou, X., Two-agent group scheduling with deteriorating jobs on a single machine, International Journal of Advanced Manufacturing Technology, 47, 657-664 (2010)
[138] Liu, P.; Yi, N.; Zhou, X., Two-agent single-machine scheduling problems under increasing linear deterioration, Applied Mathematical Modelling, 35, 2290-2296 (2011) · Zbl 1217.90108
[139] Liu, M.; Zheng, F-F; Chu, C-B; Zhang, J-T, An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration, Journal of Combinatorial Optimization, 23, 483-492 (2012) · Zbl 1244.90097
[140] Liu, M.; Zheng, F-F; Wang, S-J; Huo, J-Z, Optimal algorithms for online single machine scheduling with deteriorating jobs, Theoretical Computer Science, 445, 75-81 (2012) · Zbl 1243.68116
[141] Liu, M.; Zheng, F-F; Xu, Y-F; Wang, L., Heuristics for parallel machine scheduling with deterioration effect, Lecture Notes in Computer Science, 6831, 46-51 (2011) · Zbl 1342.90067
[142] Li, S-S; Yuan, J-J, Parallel-machine scheduling with deteriorating jobs and rejection, Theoretical Computer Science, 411, 3642-3650 (2010) · Zbl 1207.68111
[143] Li, W-X; Zhao, C-L, Deteriorating jobs scheduling on a single machine with release dates, rejection and a fixed non-availability interval, Journal of Applied Mathematics and Computation, 48, 585-605 (2015) · Zbl 1317.90125
[144] Luo, W-C; Chen, L., Approximation scheme for scheduling resumable proportionally deteriorating jobs, Lecture Notes in Computer Science, 6681, 36-45 (2011) · Zbl 1329.90066
[145] Luo, W-C; Chen, L., Approximation schemes for scheduling a maintenance and linear deteriorating jobs, Journal of Industrial and Management Optimization, 8, 271-283 (2012) · Zbl 1364.90161
[146] Luo, W-C; Ji, M., Scheduling a variable maintenance and linear deteriorating jobs on a single machine, Information Processing Letters, 115, 33-39 (2015) · Zbl 1371.90059
[147] Ma, Y.; Chu, C.; Zuo, C., A survey of scheduling with deterministic machine availability constraints, Computers and Industrial Engineering, 58, 199-211 (2010)
[148] Maniezzo, V.; Stützle, T.; Voß, S., Matheuristics: Hybrydizing metaheuristics and mathematical programming (2010), Berlin: Springer, Berlin
[149] Martello, S.; Toth, P., Knapsack problems: Algorithms and computer implementations (1990), Chichester: Wiley, Chichester · Zbl 0708.68002
[150] Ma, R.; Tao, J-P; Yuan, J-J, Online scheduling with linear deteriorating jobs to minimize the total weighted completion time, Applied Mathematics and Computation, 273, 570-583 (2016) · Zbl 1410.90091
[151] Melnikov, O. I., & Shafransky, Y. M. (1980). Parametric problem of scheduling theory. Cybernetics and Systems Analysis, 15, 352-357 (English translation of O. I. Melnikov, Y. M. Shafransky, Parametric problem of scheduling theory, Kibernetika 6, 1979, 53-57, in Russian). · Zbl 0455.90047
[152] Miao, C-X, Complexity of scheduling with proportional deterioration and release dates, Iranian Journal of Science and Technology Transaction Science, 42, 1337-1342 (2018) · Zbl 1397.90184
[153] Miao, C-X; Zhang, Y-Z; Cao, Z-G, Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs, Information Processing Letters, 111, 798-803 (2011) · Zbl 1260.68040
[154] Miao, C.; Zhang, Y.; Wu, C., Scheduling of deteriorating jobs with release dates to minimize the maximum lateness, Theoretical Computer Science, 462, 80-87 (2012) · Zbl 1252.90027
[155] Mitten, L. G., Branch-and-Bound Methods: General Formulation and Properties, Operations Research, 18, 1, 24-34 (1970) · Zbl 0225.90030
[156] Monma, Cl; Sidney, Jb, Sequencing with series-parallel precedence constraints, Mathematics of Operations Research, 4, 215-234 (1979) · Zbl 0437.90047
[157] Moore, J., An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15, 102-109 (1968) · Zbl 0164.20002
[158] Mosheiov, G., V-shaped policies for scheduling deteriorating jobs, Operations Research, 39, 979-991 (1991) · Zbl 0748.90033
[159] Mosheiov, G., Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21, 653-659 (1994) · Zbl 0810.90074
[160] Mosheiov, G., Multi-machine scheduling with linear deterioration, INFOR, 36, 205-214 (1998) · Zbl 07677568
[161] Mosheiov, G., Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics, 117, 195-209 (2002) · Zbl 1004.68031
[162] Mosheiov, G.; Sarig, A.; Sidney, J., The Browne-Yechiali single-machine sequence is optimal for flow-shops, Computers and Operations Research, 37, 1965-1967 (2010) · Zbl 1188.90104
[163] Muth, Jf; Thompson, Gl, Industrial Scheduling (1963), Englewood Cliffs: Prentice-Hall, Englewood Cliffs
[164] Nash, Jf, Non-cooperative games, Annals of Mathematics, 54, 286-295 (1951) · Zbl 0045.08202
[165] Ng, C-T; Barketau, Ms; Cheng, T-Ce; Kovalyov, My, “Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation, European Journal of Operational Research, 207, 601-604 (2010) · Zbl 1205.68174
[166] Ocetkiewicz, Km, A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem, European Journal of Operational Research, 203, 316-320 (2010) · Zbl 1177.90176
[167] Ocetkiewicz, Km, Partial dominated schedules and minimizing the total completion time of deteriorating jobs, Optimization, 62, 1341-1356 (2013) · Zbl 1282.90076
[168] Oron, D., Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times, Computers and Operations Research, 35, 2071-2078 (2008) · Zbl 1139.90012
[169] Ouazene, Y.; Yalaoui, F., Identical parallel machine scheduling with time-dependent processing times, Theoretical Computer Science, 721, 70-77 (2018) · Zbl 1390.90323
[170] Papadimitriou, Ch; Steiglitz, K., Combinatorial optimization: Algorithms and complexity (1981), Englewood Cliffs: Prentice-Hall, Englewood Cliffs
[171] Perez-Gonzalez, P.; Framinan, Jm, A common framework and taxonomy for multicriteria scheduling problem with interfering and competing jobs: Multi-agent scheduling problems, European Journal of Operational Research, 235, 1-16 (2014) · Zbl 1305.90196
[172] Picard, J-C; Queyranne, M., The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Operations Research, 26, 86-110 (1978) · Zbl 0371.90066
[173] Pinedo, Ml, Planning and scheduling in manufacturing and services (2009), Berlin: Springer, Berlin · Zbl 1175.90188
[174] Pinedo, Ml, Scheduling: Theory, algorithms, and systems (2016), Berlin: Springer, Berlin · Zbl 1332.90002
[175] Potts, Cn; Kovalyov, My, Scheduling with batching: A review, European Journal of Operations Research, 120, 228-249 (2000) · Zbl 0953.90028
[176] Potts, Cn; Strusevich, Va, Fifty years of scheduling: A survey of milestones, Journal of the Operational Research Society, 60, S41-S68 (2009) · Zbl 1168.90311
[177] Rachaniotis, Np; Pappis, Cp, Scheduling fire-fighting tasks using the concept of “deteriorating jobs”, Canadian Journal of Forest Research, 36, 652-658 (2006)
[178] Rau, Jg, Minimizing a function of permutations of \(n\) integers, Operations Research, 19, 237-240 (1971) · Zbl 0214.18701
[179] Ren, C-R; Kang, L-Y, An approximation algorithm for parallel machine scheduling with simple linear deterioration, Journal of Shanghai University, 11, 351-354 (2007) · Zbl 1141.68356
[180] Rustogi, K.; Strusevich, Va, Single machine scheduling with time-dependent linear deterioration and rate-modifying maintenance, Journal of the Operational Research Society, 66, 505-515 (2016)
[181] Schmidt, G., Scheduling on semi-identical processors, Zeitschrift für Operations Research, A28, 153-162 (1984) · Zbl 0551.90044
[182] Schmidt, G., Scheduling with limited machine availability, European Journal of Operational Research, 121, 1-15 (2000) · Zbl 0959.90023
[183] Sedding, H. A. (2018). Scheduling non-monotonous convex piecewise-linear time-dependent processing times of a uniform shape. In The 2nd international workshop on dynamic scheduling problems (pp. 79-84).
[184] Shabtay, D., Gaspar, N., & Kaspi, M. (2015). A survey of offline scheduling with rejection. Journal of Scheduling,16, 3-28 (Erratum: Journal of Scheduling 18, 2015, 329). · Zbl 1297.90058
[185] Shabtay, D.; Steiner, G., A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 155, 1643-1666 (2007) · Zbl 1119.90022
[186] Shafransky, Ym, On optimal sequencing for deterministic systems with a tree-like partial order, Vestsii Akademii Navuk BSSR, 2, 120 (1978) · Zbl 0386.90027
[187] 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, International Journal of Advanced Manufacturing Technology, 34, 774-782 (2007)
[188] Shioura, A.; Shakhlevich, Nv; Strusevich, Va, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches, European Journal of Operational Research, 266, 795-818 (2018) · Zbl 1403.90365
[189] Smith, We, Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956)
[190] Strusevich, Va; Hall, La, An open shop scheduling problem with a non-bottleneck machine, Operations Research Letters, 21, 11-18 (1997) · Zbl 0885.90061
[191] Strusevich, Va; Rustogi, K., Scheduling with time-changing effects and rate-modifying activities (2017), Berlin: Springer, Berlin · Zbl 1357.90003
[192] Sundararaghavan, Ps; Kunnathur, As, Single machine scheduling with start time dependent processing times: Some solvable cases, European Journal of Operational Research, 78, 394-403 (1994) · Zbl 0816.90088
[193] Sun, L-H; Sun, L-Y; Cui, K.; Wang, J-B, A note on flow shop scheduling problems with deteriorating jobs on no-idle dominant machines, European Journal of Operational Research, 200, 309-311 (2010) · Zbl 1183.90192
[194] Sun, L-H; Sun, L-Y; Wang, M-Z; Wang, J-B, Flow shop makespan minimization scheduling with deteriorating jobs under dominating machines, International Journal of Production Economics, 138, 195-200 (2012)
[195] Tanaev, V. S., Gordon, V. S., & Shafransky, Y. M. (1994a). Scheduling theory: Single-stage systems. Dordrecht: Kluwer (English translation of V. S. Tanaev, Y. N. Sotskov, V. A. Strusevich, Scheduling Theory: Single-Stage Systems, Nauka, Moscow, 1984, in Russian). · Zbl 0827.90079
[196] Tanaev, V. S., Sotskov, Y. N., & Strusevich, V. A. (1994b). Scheduling theory: Multi-stage systems. Kluwer, Dordrecht (English translation of V. S. Tanaev, Y. N. Sotskov, V. A. Strusevich, Scheduling Theory: Multi-Stage Systems, Nauka, Moscow, 1989, in Russian). · Zbl 0673.90023
[197] Tang, L.; Zhao, X.; Liu, J-Y; Leung, Jy-T, Competitive two-agent scheduling with deteriorating jobs on a single and parallel-batching machine, European Journal of Operational Research, 263, 401-411 (2017) · Zbl 1380.90130
[198] Thörnblad, K.; Patriksson, M., A note on the complexity of flow-shop scheduling with deteriorating jobs, Discrete Applied Mathematics, 159, 251-253 (2011) · Zbl 1208.90079
[199] T’Kindt, V.; Billaut, J-C, Multicriteria scheduling: Theory, models and algorithms (2006), Berlin: Springer, Berlin · Zbl 1126.90002
[200] Toksarı, Md; Güner, E., The common due-date early/tardy scheduling problem on a parallel machine under the effects of time-dependent learning and linear and nonlinear deterioration, Expert Systems with Applications, 37, 92-112 (2010)
[201] Tzafestas, Sg, Computer-assisted management and control of manufacturing systems (1997), Berlin: Springer, Berlin
[202] Valdes, J.; Tarjan, Re; Lawler, El, The recognition of series parallel digraphs, SIAM Journal on Computing, 11, 289-313 (1982) · Zbl 0478.68065
[203] Voutsinas, Tg; Pappis, Cp, Scheduling jobs with values exponentially deteriorating over time, International Journal of Production Economics, 79, 163-169 (2002)
[204] Wajs, W., Polynomial algorithm for dynamic sequencing problem, Archiwum Automatyki i Telemechaniki, 31, 209-213 (1986) · Zbl 0609.90064
[205] Wang, J-B, Single machine scheduling with decreasing linear deterioration under precedence constraints, Computers and Mathematics with Applications, 58, 95-103 (2009) · Zbl 1189.90069
[206] Wang, J-B, Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan, International Journal of Advanced Manufacturing Technology, 48, 719-723 (2010)
[207] Wang, J-B; Ng, C-T; Cheng, T-Ce, Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint, Computers and Operations Research, 35, 2684-2693 (2008) · Zbl 1180.90143
[208] Wang, L.; Sun, L-Y; Sun, L-H; Wang, J-B, On three-machine flow shop scheduling with deteriorating jobs, International Journal of Production Economics, 125, 185-189 (2010)
[209] Wang, J-B; Wang, M-Z, Single-machine scheduling with nonlinear deterioration, Optimization Letters, 6, 87-98 (2012) · Zbl 1259.90040
[210] Wang, J-B; Wang, M-Z, Minimizing makespan in three-machine flow shops with deteriorating jobs, Computers and Operations Research, 40, 547-557 (2013) · Zbl 1349.90410
[211] Wang, J-B; Wang, J-J, Single machine group scheduling with time dependent processing times and ready times, Information Sciences, 275, 226-231 (2014) · Zbl 1341.90057
[212] Wang, J-B; Wang, J-J, Single-machine scheduling problems with precedence constraints and simple linear deterioration, Applied Mathematical Modelling, 39, 1172-1182 (2015) · Zbl 1432.90065
[213] Wang, J-B; Wang, J-J; Ji, P., Scheduling jobs with chain precedence constraints and deteriorating jobs, Journal of the Operational Research Society, 62, 1765-1770 (2011)
[214] Wang, J-B; Xia, Z-X, Scheduling jobs under decreasing linear deterioration, Information Processing Letters, 94, 63-69 (2005) · Zbl 1182.68359
[215] Woeginger, Gj, When does a dynamic programming formulation guarantee the existence of an FPTAS?, INFORMS Journal on Computing, 12, 57-73 (2000) · Zbl 1034.90014
[216] Woeginger, Gj, Exact algorithms for NP-hard problems: A survey, Lecture Notes in Computer Science, 2570, 187-205 (2003)
[217] Wu, Y.; Dong, M.; Zheng, Z., Patient scheduling with periodic deteriorating maintenance on single medical device, Computers and Operations Research, 49, 107-116 (2014) · Zbl 1349.90418
[218] Wu, C-C; Lee, W-C, Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine, Information Processing Letters, 87, 89-93 (2003) · Zbl 1161.68367
[219] Wu, C-C; Lee, W-C; Shiau, Y-R, Minimizing the total weighted completion time on a single machine under linear deterioration, International Journal of Advanced Manufacturing Technology, 33, 1237-1243 (2007)
[220] Yin, Y-Q; Cheng, T-Ce; Wan, L.; Wu, C-C; Liu, J., Two-agent single-machine scheduling with deteriorating jobs, Computers and Industrial Engineering, 81, 177-185 (2015)
[221] Yin, Y-Q; Cheng, S-R; Wu, C-C, Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties, Information Sciences, 189, 282-292 (2012) · Zbl 1247.90165
[222] Yin, Y-Q; Xu, D-H, Some single-machine scheduling problems with general effects of learning and deterioration, Computers and Mathematics with Applications, 61, 100-108 (2011) · Zbl 1207.90060
[223] Yu, S.; Ojiaku, J-T; Wong, Pw-H; Xu, Y., Online makespan scheduling of linear deteriorating jobs on parallel machines, Lecture Notes in Computer Science, 7287, 260-272 (2012) · Zbl 1354.90056
[224] Yu, S.; Wong, Pw-H, Online scheduling of simple linear deteriorating jobs to minimize the total general completion time, Theoretical Computer Science, 487, 95-102 (2013) · Zbl 1310.68257
[225] Zhang, X-G; Wang, H.; Wang, X-P, Patient scheduling problems with deferred deteriorated functions, Journal of Combinatorial Optimization, 30, 1027-1041 (2015) · Zbl 1330.90039
[226] Zhao, C-L; Tang, H-Y, Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints, International Journal of Production Economics, 136, 131-136 (2012)
[227] Zhao, C-L; Tang, H-Y, Parallel machines scheduling with deteriorating jobs and availability constraints, Japan Journal of Industrial and Applied Mathematics, 31, 501-512 (2014) · Zbl 1308.90070
[228] Zou, J.; Zhang, Y-Z; Miao, C-X, Uniform parallel-machine scheduling with time dependent processing times, Journal of the Operational Research Society China, 1, 239-252 (2013) · Zbl 1334.90058
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.