nach oben

Journal of Scheduling

Erschienen in:

28.01.2020

A review of four decades of time-dependent scheduling: main results, new topics, and open problems

verfasst von: Stanisław Gawiejnowicz

Erschienen in: Journal of Scheduling | Ausgabe 1/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Journal of scheduling (2020)

Nächster Artikel Metaheuristics for solving a multi-objective flow shop scheduling problem with sequence-dependent setup times

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Achugbue, J. O., & Chin, F. Y. (1982). Scheduling the open shop to minimize mean flow time. SIAM Journal on Computing, 11, 709–720.

Agnetis, A., Billaut, J.-C., Gawiejnowicz, S., Pacciarelli, D., & Soukhal, A. (2014). Multi-agent Scheduling: Models and Algorithms. Berlin: Springer.

Agnetis, A., Mirchandani, P., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52, 229–242.

Albers, S. (2010). Online scheduling. In Y. Robert & F. Vivien (Eds.), Introduction to scheduling (pp. 51–57). Boca Raton: Chapmann and Hall.

Alidaee, B. (1990). 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.

Alidaee, B., & Womer, N. K. (1999). Scheduling with time dependent processing times: Review and extensions. Journal of the Operational Research Society, 50, 711–720.

Arigliano, A., Ghiani, G., Grieco, A., & Guerriero, E. (2017). Single-machine time-dependent scheduling problems with fixed rate-modifying activities and resumable jobs, 4OR-Q. Journal of Operations Research, 15, 201–215.

Bachman, A., & Janiak, A. (2000). Minimizing maximum lateness under linear deterioration. European Journal of Operational Research, 126, 557–566.

Bachman, A., Janiak, A., & Kovalyov, M. Y. (2002). Minimizing the total weighted completion time of deteriorating jobs. Information Processing Letters, 81, 81–84.

Baker, K., & Smith, J. C. (2003). A multiple criterion model for machine scheduling. Journal of Scheduling, 6, 7–16.

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).

Barketau, M. S., Cheng, T.-C. E., Ng, C. T., Kotov, V., & Kovalyov, M. Y. (2008). Batch scheduling of step deteriorating jobs. Journal of Scheduling, 11, 17–28.

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).

Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G., Sterna, M., & Weglarz, J. (2019). Handbook on scheduling: from applications to theory. Berlin: Springer.

Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling: from theory to applications. Berlin: Springer.

Bosio, A., & Righini, G. (2009). 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.

Browne, S., & Yechiali, U. (1990). Scheduling deteriorating jobs on a single processor. Operations Research, 38, 495–498.

Burkard, R., Dell’Amico, M., & Martello, S. (2012). Assignment problems, revised reprint. Philadelphia: SIAM.

Cai, P., Cai, J.-Y., & Naik, A. V. (1998a). Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns. Journal of Combinatorial Optimization, 1, 367–376.

Cai, J.-Y., Cai, P., & Zhu, Y. (1998b). On a scheduling problem of time deteriorating jobs. Journal of Complexity, 14, 190–209.

Chen, Z.-L. (1995). A note on single-processor scheduling with time-dependent execution times. Operations Research Letters, 17, 127–129.

Chen, Z.-L. (1996). Parallel machine scheduling with time dependent processing times. Discrete Applied Mathematics,70, 81–93 (Erratum: Discrete Applied Mathematics 75, 1996, 103).

Cheng, T.-C. E., & Ding, Q. (1998). The complexity of scheduling starting time dependent tasks with release times. Information Processing Letters, 65, 75–79.

Cheng, T.-C. E., & Ding, Q. (1999). The time dependent makespan problem is strongly NP-complete. Computers and Operations Research, 26, 749–754.

Cheng, T.-C. E., & Ding, Q. (2000). Single machine scheduling with deadlines and increasing rates of processing times. Acta Informatica, 36, 673–692.

Cheng, T.-C. E., & Ding, Q. (2003). Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine. Computers and Operations Research, 30, 51–62.

Cheng, T.-C. E., Ding, Q., & Lin, B. M.-T. (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152, 1–13.

Cheng, T.-C. E., He, Y., Hoogeveen, H., Ji, M., & Woeginger, G. (2006). Scheduling with step-improving processing times. Operations Research Letters, 34, 37–40.

Cheng, T.-C. E., Shafransky, Y., & Ng, C.-T. (2016). An alternative approach for proving the NP-hardness of optimization problems. European Journal of Operational Research, 248, 52–58.

Cheng, M.-B., & Sun, S.-J. (2007). A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs. Journal of Shanghai University, 11, 451–456.

Cheng, Y.-S., & Sun, S.-J. (2009). Scheduling linear deteriorating jobs with rejection on a single machine. European Journal of Operational Research, 194, 18–27.

Cheng, M.-B., Sun, S.-J., & He, L.-M. (2007). Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines. European Journal of Operational Research, 183, 115–124.

Cheng, M.-B., Tadikamalla, P. R., Shang, J., & Zhang, B. (2015). 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.

Cheng, M.-B., Tadikamalla, P. R., Shang, J., & Zhang, S.-Q. (2014). Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs. European Journal of Operational Research, 234, 650–657.

Cheng, M.-B., Wang, G.-Q., & He, L.-M. (2009). Parallel machine scheduling problems with proportionally deteriorating jobs. International Journal of Systems Science, 40, 53–57.

Chen, Q., Lin, L., Tan, Z., & Yan, Y. (2017). Coordination mechanisms for scheduling games with proportional deterioration. European Journal of Operational Research, 263, 380–389.

Chryssolouris, G. (2006). Manufacturing systems: Theory and practice. Berlin: Springer.

Conway, R. W., Maxwell, W. L., & Miller, L. W. (1967). Theory of scheduling. Reading: Addison-Wesley.

Dȩbczyński, M. (2014). Maximum cost scheduling of jobs with mixed variable processing times and k-partite precedence constraints. Optimization Letters, 8, 395–400.

Dȩbczyński, M., & Gawiejnowicz, S. (2013). Scheduling jobs with mixed processing times, arbitrary precedence constraints and maximum cost criterion. Computers and Industrial Engineering, 64, 273–279.

Dror, M., Kubiak, W., & Dell’Olmo, P. (1997). Scheduling chains to minimize mean flow time. Information Processing Letters, 61, 297–301.

Du, J., & Leung, J. Y.-T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15, 483–495.

Fan, B., Li, S., Zhou, L., & Zhang, L. (2011). Scheduling resumable deteriorating jobs on a single machine with non-availability constraints. Theoretical Computer Science, 412, 275–280.

Fiat, A., & Woeginger, G. (Eds.). (1998). Online algorithms: The state of the art. Berlin: Springer.

Fiszman, S., & Mosheiov, G. (2018). Minimizing total load on a proportionate flowshop with position-dependent processing times and rejection. Information Processing Letters, 132, 39–43.

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W. H. Freeman.

Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1, 117–129.

Gawiejnowicz, S. (1996a). A note on scheduling on a single processor with speed dependent on a number of executed jobs. Information Processing Letters, 57, 297–300.

Gawiejnowicz, S. (1996b). Brief survey of continuous models of scheduling. Foundations of Computing and Decision Sciences, 21, 81–100.

Gawiejnowicz, S. (1997). Scheduling jobs with varying processing times. Poznań: Poznań University of Technology. (in Polish).

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).

Gawiejnowicz, S. (2007). Scheduling deteriorating jobs subject to job or machine availability constraints. European Journal of Operational Research, 180, 472–478.

Gawiejnowicz, S. (2008). Time-dependent scheduling. Berlin: Springer.

Gawiejnowicz, S. (2020). Models and algorithms of time-dependent scheduling. Berlin: Springer.

Gawiejnowicz, S., & Kononov, A. (2010). Complexity and approximability of scheduling resumable proportionally deteriorating jobs. European Journal of Operational Research, 200, 305–308.

Gawiejnowicz, S., & Kononov, A. (2014). Isomorphic scheduling problems. Annals of Operations Research, 213, 131–145.

Gawiejnowicz, S., & Kurc, W. (2015). Structural properties of time-dependent scheduling problems with the norm objective. Omega-International Journal of Management Science, 57, 196–202.

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).

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).

Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2002). A greedy approach for a time-dependent scheduling problem. Lecture Notes in Computer Science, 2328, 79–86.

Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2004). Minimizing time-dependent total completion time on parallel identical machines. Lecture Notes in Computer Science, 3019, 89–96.

Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2006a). Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences. Discrete Applied Mathematics, 154, 2150–2166.

Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2006b). Parallel machine scheduling of deteriorating jobs by modified steepest descent search. Lecture Notes in Computer Science, 3911, 116–123.

Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2006c). Pareto and scalar bicriterion scheduling of deteriorating jobs. Computers and Operations Research, 33, 746–767.

Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2009a). Equivalent time-dependent scheduling problems. European Journal of Operational Research, 196, 919–929.

Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2009b). Conjugate problems in time-dependent scheduling. Journal of Scheduling, 12, 543–553.

Gawiejnowicz, S., Lai, T.-C., & Chiang, M.-H. (2011a). Scheduling linearly shortening jobs under precedence constraints. Applied Mathematical Modelling, 35, 2005–2015.

Gawiejnowicz, S., Lee, W.-C., Lin, C.-L., & Wu, C.-C. (2011b). Single-machine scheduling of proportionally deteriorating jobs by two agents. Journal of the Operational Research Society, 62, 1983–1991.

Gawiejnowicz, S., & Lin, B. M.-T. (2010). Scheduling time-dependent jobs under mixed deterioration. Applied Mathematics and Computation, 216, 438–447.

Gawiejnowicz, S., & Pankowska, L. (1995). Scheduling jobs with varying processing times. Information Processing Letters, 54, 175–178.

Gawiejnowicz, S., & Suwalski, C. (2014). Scheduling linearly deteriorating jobs by two agents to minimize the weighted sum of two criteria. Computers and Operations Research, 52, 135–146.

Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of ACM, 23, 665–679.

Gordon, V. S., Potts, C. N., Strusevich, V. A., & Whitehead, J. D. (2008). Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation. Journal of Scheduling, 11, 357–370.

Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell Labs Technical Journal, 45, 1563–1581.

Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17, 416–429.

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.

Gupta, J. N. D., & Gupta, S. K. (1988). Single facility scheduling with nonlinear processing times. Computers and Industrial Engineering, 14, 387–393.

Gupta, S. K., Kunnathur, A. S., & Dandapani, K. (1987). Optimal repayment policies for multiple loans. Omega-International Journal of Management Science, 15, 323–330.

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).

Halman, N., Klabjan, D., Li, C.-L., Orlin, J., & Simchi-Levi, D. (2014). Fully polynomial time approximation schemes for stochastic dynamic programs. SIAM Journal on Discrete Mathematics, 28, 1725–1796.

Halman, N., Klabjan, D., Mostagir, M., Orlin, J., & Simchi-Levi, D. (2009). A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Mathematics of Operations Research, 34, 674–685.

Hardy, G., Littlewood, J. E., & Polya, G. (1934). Inequalities. London: Cambridge University Press.

He, C., & Leung, J. Y.-T. (2017). Two-agent scheduling of deteriorating jobs. Journal of Combinatorial Optimization, 34, 362–367.

Ho, J., & Gupta, J. N. D. (1995). Flowshop scheduling with dominant machines. Computers and Operations Research, 22, 237–246.

Ho, J., & Wong, J. (1995). Makespan minimization for m parallel identical processors. Naval Research Logistics, 42, 935–948.

Ho, K. I.-J., Leung, J. Y.-T., & Wei, W.-D. (1993). Complexity of scheduling tasks with time-dependent execution times. Information Processing Letters, 48, 315–320.

Holloway, C. A., & Nelson, R. T. (1974). Job shop scheduling with due dates and variable processing times. Management Science, 20, 1264–1275.

Hsieh, Y.-C., & Bricker, D. L. (1997). Scheduling linearly deteriorating jobs on multiple machines. Computers and Industrial Engineering, 32, 727–734.

Jaehn, F., & Sedding, H. A. (2016). Scheduling with time-dependent discrepancy times. Journal of Scheduling, 19, 737–757.

Jafari, A.-A., Khademi-Zare, H., Lotfi, M. M., & Tavakkoli-Moghaddam, R. (2017). A note on “On three-machine flow shop scheduling with deteriorating jobs”. International Journal of Production Economics, 191, 250–252.

Ji, M., & Cheng, T.-C. E. (2007). An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan. Information Processing Letters, 102, 41–47.

Ji, M., & Cheng, T.-C. E. (2008). Parallel-machine scheduling with simple linear deterioration to minimize total completion time. European Journal of Operational Research, 188, 342–347.

Ji, M., & Cheng, T.-C. E. (2009). Parallel-machine scheduling of simple linear deteriorating jobs. Theoretical Computer Science, 410, 3761–3768.

Ji, M., & Cheng, T.-C. E. (2010). Scheduling resumable simple linear deteriorating jobs on a single machine with an availability constraint to minimize makespan. Computers and Industrial Engineering, 59, 794–798.

Ji, M., He, Y., & Cheng, T.-C. E. (2006). Scheduling linear deteriorating jobs with an availability constraint on a single machine. Theoretical Computer Science, 362, 115–126.

Johnson, S. M. (1954). Optimal two and three stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61–68.

Johnson, D. S. (1982). The NP-completeness column: An ongoing guide. Journal of Algorithms, 2, 393–405.

Kacem, I., & Levner, E. (2016). An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs. Journal of Industrial and Management Optimization, 12, 811–817.

Kang, L.-Y., Cheng, T.-C. E., Ng, C.-T., & Zhao, M. (2005). Scheduling to minimize makespan with time-dependent processing times. Lecture Notes in Computer Science, 3827, 925–933.

Kang, L.-Y., & Ng, C.-T. (2007). A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs. International Journal of Production Economics, 109, 180–184.

Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum Press.

Kawase, Y., Makino, K., & Seimi, K. (2018). Optimal composition ordering problems for piecewise linear functions. Algorithmica, 80, 2134–2159.

Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Berlin: Springer.

Kelly, F. P. (1982). A remark on search and sequencing problems. Mathematics of Operations Research, 7, 154–157.

Klamroth, K., & Wiecek, M. (2001). A time-dependent multiple criteria single-machine scheduling problem. European Journal of Operational Research, 135, 17–26.

Kohler, W. H., & Steiglitz, K. (1976). Enumerative and iterative computational approaches. In E. G. Coffman Jr. (Ed.), Computer and Job-Shop Scheduling Theory. New York: Wiley.

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).

Kononov, A. (1996). Combinatorial complexity of scheduling jobs with simple linear deterioration. Discrete Analysis and Operations Research, 3, 15–32. (in Russian).

Kononov, A. (1997). Scheduling problems with linear increasing processing times. In U. Zimmermann, et al. (Eds.), Operations research 1996 (pp. 208–212). Berlin: Springer.

Kononov, A. (1998). Single machine scheduling problems with processing times proportional to an arbitrary function. Discrete Analysis and Operations Research, 5, 17–37. (in Russian).

Kononov, A., & Gawiejnowicz, S. (2001). NP-hard cases in scheduling deteriorating jobs on dedicated machines. Journal of the Operational Research Society, 52, 708–718.

Korte, B., & Vygen, J. (2018). Combinatorial Optimization: Theory and Algorithms (6th ed.). Berlin: Springer.

Koulamas, C. (2010). The single-machine total tardiness scheduling problem: Review and extensions. European Journal of Operational Research, 202, 1–7.

Koutsoupias, E., & Papadimitriou, C. (2009). Worst-case equilibria. Computer Science Review, 3, 65–69.

Kovalyov, M. Y., & Kubiak, W. (1998). A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs. Journal of Heuristics, 3, 287–297.

Kubale, M., & Ocetkiewicz, K. (2009). A new optimal algorithm for a time-dependent scheduling problem. Control and Cybernets, 38, 713–721.

Kubiak, W., & van de Velde, S. L. (1998). Scheduling deteriorating jobs to minimize makespan. Naval Research Logistics, 45, 511–523.

Kunnathur, A. S., & Gupta, S. K. (1990). 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.

Kuo, W.-H., Hsu, C.-J., & Yang, D.-L. (2009). A note on unrelated parallel machine scheduling with time-dependent processing times. Journal of the Operational Research Society, 60, 431–434.

Kuo, W.-H., & Yang, D.-L. (2007). Single-machine scheduling problems with start-time dependent processing time. Computers and Mathematics with Applications, 53, 1658–1664.

Kuo, W.-H., & Yang, D.-L. (2008). Parallel-machine scheduling with time-dependent processing times. Theoretical Computer Science, 393, 204–210.

Kuo, W.-H., & Yang, D.-L. (2012). Single-machine scheduling with deteriorating jobs. International Journal of Systems Science, 43, 132–139.

Lawler, E. L. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management of Science, 19, 544–546.

Lawler, E. L. (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics, 2, 75–90.

Lawler, E. L., & Woods, D. E. (1966). Branch-and-bound methods: A survey. Operations Research, 14, 699–719.

Lee, C.-Y., & Leon, V. J. (2001). Machine scheduling with a rate-modifying activity. European Journal of Operational Research, 128, 119–128.

Lee, W.-C., Shiau, Y.-R., Chen, S.-K., & Wu, C.-C. (2010a). A two-machine flowshop scheduling problem with deteriorating jobs and blocking. International Journal of Production Economics, 124, 188–197.

Lee, W.-C., Wang, W.-J., Shiau, Y.-R., & Wu, C.-C. (2010b). A single-machine scheduling problem with two-agent and deteriorating jobs. Applied Mathematical Modelling, 34, 3098–3107.

Lee, W.-C., Wu, C.-C., & Chung, Y.-H. (2008a). Scheduling deteriorating jobs on a single machine with release times. Computers and Industrial Engineering, 54, 441–452.

Lee, W.-C., Wu, C.-C., Wen, C.-C., & Chung, Y.-H. (2008b). A two-machine flowshop makespan scheduling problem with deteriorating jobs. Computers and Industrial Engineering, 54, 737–749.

Leung, J. Y.-T. (Ed.). (2004). Handbook of scheduling: Models, algorithms and performance analysis. New York: Chappman & Hall.

Leung, J. Y.-T., Ng, C.-T., & Cheng, T.-C. E. (2008). Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times. European Journal of Operational Research, 187, 1090–1099.

Li, S.-S. (2011). Scheduling proportionally deteriorating jobs in two-machine open shop with a non-bottleneck machine. Asia-Pacific Journal of Operations Research, 28, 623–631.

Li, K., Liu, C., & Li, K. (2014). An approximation algorithm based on game theory for scheduling simple linear deteriorating jobs. Theoretical Computer Science, 543, 46–51.

Li, S.-S., Ng, C.-T., Cheng, T.-C. E., & Yuan, J.-J. (2011). Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan. European Journal of Operational Research, 210, 482–488.

Liu, P., & Tang, L. (2008). Two-agent scheduling with linear deteriorating jobs on a single machine. Lecture Notes in Computer Science, 5092, 642–650.

Liu, P., Tang, L., & Zhou, X. (2010). Two-agent group scheduling with deteriorating jobs on a single machine. International Journal of Advanced Manufacturing Technology, 47, 657–664.

Liu, P., Yi, N., & Zhou, X. (2011). Two-agent single-machine scheduling problems under increasing linear deterioration. Applied Mathematical Modelling, 35, 2290–2296.

Liu, M., Zheng, F.-F., Chu, C.-B., & Zhang, J.-T. (2012a). An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration. Journal of Combinatorial Optimization, 23, 483–492.

Liu, M., Zheng, F.-F., Wang, S.-J., & Huo, J.-Z. (2012b). Optimal algorithms for online single machine scheduling with deteriorating jobs. Theoretical Computer Science, 445, 75–81.

Liu, M., Zheng, F.-F., Xu, Y.-F., & Wang, L. (2011). Heuristics for parallel machine scheduling with deterioration effect. Lecture Notes in Computer Science, 6831, 46–51.

Li, S.-S., & Yuan, J.-J. (2010). Parallel-machine scheduling with deteriorating jobs and rejection. Theoretical Computer Science, 411, 3642–3650.

Li, W.-X., & Zhao, C.-L. (2015). 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.

Luo, W.-C., & Chen, L. (2011). Approximation scheme for scheduling resumable proportionally deteriorating jobs. Lecture Notes in Computer Science, 6681, 36–45.

Luo, W.-C., & Chen, L. (2012). Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial and Management Optimization, 8, 271–283.

Luo, W.-C., & Ji, M. (2015). Scheduling a variable maintenance and linear deteriorating jobs on a single machine. Information Processing Letters, 115, 33–39.

Ma, Y., Chu, C., & Zuo, C. (2010). A survey of scheduling with deterministic machine availability constraints. Computers and Industrial Engineering, 58, 199–211.

Maniezzo, V., Stützle, T., & Voß, S. (Eds.). (2010). Matheuristics: Hybrydizing metaheuristics and mathematical programming. Berlin: Springer.

Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementations. Chichester: Wiley.

Ma, R., Tao, J.-P., & Yuan, J.-J. (2016). Online scheduling with linear deteriorating jobs to minimize the total weighted completion time. Applied Mathematics and Computation, 273, 570–583.

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).

Miao, C.-X. (2018). Complexity of scheduling with proportional deterioration and release dates. Iranian Journal of Science and Technology Transaction Science, 42, 1337–1342.

Miao, C.-X., Zhang, Y.-Z., & Cao, Z.-G. (2011). Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs. Information Processing Letters, 111, 798–803.

Miao, C., Zhang, Y., & Wu, C. (2012). Scheduling of deteriorating jobs with release dates to minimize the maximum lateness. Theoretical Computer Science, 462, 80–87.

Mitten, L. (1970). Branch-and-bound methods: General formulation and properties. Operations Research,18, 24–34 (Erratum: Operations Research 19, 1971, 550).

Monma, C. L., & Sidney, J. B. (1979). Sequencing with series-parallel precedence constraints. Mathematics of Operations Research, 4, 215–234.

Moore, J. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15, 102–109.

Mosheiov, G. (1991). V-shaped policies for scheduling deteriorating jobs. Operations Research, 39, 979–991.

Mosheiov, G. (1994). Scheduling jobs under simple linear deterioration. Computers and Operations Research, 21, 653–659.

Mosheiov, G. (1998). Multi-machine scheduling with linear deterioration. INFOR, 36, 205–214.

Mosheiov, G. (2002). Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete Applied Mathematics, 117, 195–209.

Mosheiov, G., Sarig, A., & Sidney, J. (2010). The Browne–Yechiali single-machine sequence is optimal for flow-shops. Computers and Operations Research, 37, 1965–1967.

Muth, J. F., & Thompson, G. L. (1963). Industrial Scheduling. Englewood Cliffs: Prentice-Hall.

Nash, J. F. (1951). Non-cooperative games. Annals of Mathematics, 54, 286–295.

Ng, C.-T., Barketau, M. S., Cheng, T.-C. E., & Kovalyov, M. Y. (2010). “Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation. European Journal of Operational Research, 207, 601–604.

Ocetkiewicz, K. M. (2010). A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem. European Journal of Operational Research, 203, 316–320.

Ocetkiewicz, K. M. (2013). Partial dominated schedules and minimizing the total completion time of deteriorating jobs. Optimization, 62, 1341–1356.

Oron, D. (2008). Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times. Computers and Operations Research, 35, 2071–2078.

Ouazene, Y., & Yalaoui, F. (2018). Identical parallel machine scheduling with time-dependent processing times. Theoretical Computer Science, 721, 70–77.

Papadimitriou, C. H., & Steiglitz, K. (1981). Combinatorial optimization: Algorithms and complexity. Englewood Cliffs: Prentice-Hall.

Perez-Gonzalez, P., & Framinan, J. M. (2014). 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.

Picard, J.-C., & Queyranne, M. (1978). The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Operations Research, 26, 86–110.

Pinedo, M. L. (2009). Planning and scheduling in manufacturing and services (2nd ed.). Berlin: Springer.

Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Berlin: Springer.

Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: A review. European Journal of Operations Research, 120, 228–249.

Potts, C. N., & Strusevich, V. A. (2009). Fifty years of scheduling: A survey of milestones. Journal of the Operational Research Society, 60, S41–S68.

Rachaniotis, N. P., & Pappis, C. P. (2006). Scheduling fire-fighting tasks using the concept of “deteriorating jobs”. Canadian Journal of Forest Research, 36, 652–658.

Rau, J. G. (1971). Minimizing a function of permutations of \(n\) integers. Operations Research, 19, 237–240.

Ren, C.-R., & Kang, L.-Y. (2007). An approximation algorithm for parallel machine scheduling with simple linear deterioration. Journal of Shanghai University, 11, 351–354.

Rustogi, K., & Strusevich, V. A. (2016). Single machine scheduling with time-dependent linear deterioration and rate-modifying maintenance. Journal of the Operational Research Society, 66, 505–515.

Schmidt, G. (1984). Scheduling on semi-identical processors. Zeitschrift für Operations Research, A28, 153–162.

Schmidt, G. (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121, 1–15.

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).

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).

Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643–1666.

Shafransky, Y. M. (1978). On optimal sequencing for deterministic systems with a tree-like partial order. Vestsii Akademii Navuk BSSR, 2, 120.

Shiau, Y.-R., Lee, W.-C., Wu, C.-C., & Chang, C.-M. (2007). Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration. International Journal of Advanced Manufacturing Technology, 34, 774–782.

Shioura, A., Shakhlevich, N. V., & Strusevich, V. A. (2018). 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.

Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3, 59–66.

Strusevich, V. A., & Hall, L. A. (1997). An open shop scheduling problem with a non-bottleneck machine. Operations Research Letters, 21, 11–18.

Strusevich, V. A., & Rustogi, K. (2017). Scheduling with time-changing effects and rate-modifying activities. Berlin: Springer.

Sundararaghavan, P. S., & Kunnathur, A. S. (1994). Single machine scheduling with start time dependent processing times: Some solvable cases. European Journal of Operational Research, 78, 394–403.

Sun, L.-H., Sun, L.-Y., Cui, K., & Wang, J.-B. (2010). A note on flow shop scheduling problems with deteriorating jobs on no-idle dominant machines. European Journal of Operational Research, 200, 309–311.

Sun, L.-H., Sun, L.-Y., Wang, M.-Z., & Wang, J.-B. (2012). Flow shop makespan minimization scheduling with deteriorating jobs under dominating machines. International Journal of Production Economics, 138, 195–200.

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).

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).

Tang, L., Zhao, X., Liu, J.-Y., & Leung, J. Y.-T. (2017). Competitive two-agent scheduling with deteriorating jobs on a single and parallel-batching machine. European Journal of Operational Research, 263, 401–411.

Thörnblad, K., & Patriksson, M. (2011). A note on the complexity of flow-shop scheduling with deteriorating jobs. Discrete Applied Mathematics, 159, 251–253.

T’kindt, V., & Billaut, J.-C. (2006). Multicriteria scheduling: Theory, models and algorithms (2nd ed.). Berlin: Springer.

Toksarı, M. D., & Güner, E. (2010). 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.

Tzafestas, S. G. (Ed.). (1997). Computer-assisted management and control of manufacturing systems. Berlin: Springer.

Valdes, J., Tarjan, R. E., & Lawler, E. L. (1982). The recognition of series parallel digraphs. SIAM Journal on Computing, 11, 289–313.

Voutsinas, T. G., & Pappis, C. P. (2002). Scheduling jobs with values exponentially deteriorating over time. International Journal of Production Economics, 79, 163–169.

Wajs, W. (1986). Polynomial algorithm for dynamic sequencing problem. Archiwum Automatyki i Telemechaniki, 31, 209–213. (in Polish).

Wang, J.-B. (2009). Single machine scheduling with decreasing linear deterioration under precedence constraints. Computers and Mathematics with Applications, 58, 95–103.

Wang, J.-B. (2010). Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan. International Journal of Advanced Manufacturing Technology, 48, 719–723.

Wang, J.-B., Ng, C.-T., & Cheng, T.-C. E. (2008). Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint. Computers and Operations Research, 35, 2684–2693.

Wang, L., Sun, L.-Y., Sun, L.-H., & Wang, J.-B. (2010). On three-machine flow shop scheduling with deteriorating jobs. International Journal of Production Economics, 125, 185–189.

Wang, J.-B., & Wang, M.-Z. (2012). Single-machine scheduling with nonlinear deterioration. Optimization Letters, 6, 87–98.

Wang, J.-B., & Wang, M.-Z. (2013). Minimizing makespan in three-machine flow shops with deteriorating jobs. Computers and Operations Research, 40, 547–557.

Wang, J.-B., & Wang, J.-J. (2014). Single machine group scheduling with time dependent processing times and ready times. Information Sciences, 275, 226–231.

Wang, J.-B., & Wang, J.-J. (2015). Single-machine scheduling problems with precedence constraints and simple linear deterioration. Applied Mathematical Modelling, 39, 1172–1182.

Wang, J.-B., Wang, J.-J., & Ji, P. (2011). Scheduling jobs with chain precedence constraints and deteriorating jobs. Journal of the Operational Research Society, 62, 1765–1770.

Wang, J.-B., & Xia, Z.-X. (2005). Scheduling jobs under decreasing linear deterioration. Information Processing Letters, 94, 63–69.

Woeginger, G. J. (2000). When does a dynamic programming formulation guarantee the existence of an FPTAS? INFORMS Journal on Computing, 12, 57–73.

Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey. Lecture Notes in Computer Science, 2570, 187–205.

Wu, Y., Dong, M., & Zheng, Z. (2014). Patient scheduling with periodic deteriorating maintenance on single medical device. Computers and Operations Research, 49, 107–116.

Wu, C.-C., & Lee, W.-C. (2003). Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine. Information Processing Letters, 87, 89–93.

Wu, C.-C., Lee, W.-C., & Shiau, Y.-R. (2007). Minimizing the total weighted completion time on a single machine under linear deterioration. International Journal of Advanced Manufacturing Technology, 33, 1237–1243.

Yin, Y.-Q., Cheng, T.-C. E., Wan, L., Wu, C.-C., & Liu, J. (2015). Two-agent single-machine scheduling with deteriorating jobs. Computers and Industrial Engineering, 81, 177–185.

Yin, Y.-Q., Cheng, S.-R., & Wu, C.-C. (2012). Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Information Sciences, 189, 282–292.

Yin, Y.-Q., & Xu, D.-H. (2011). Some single-machine scheduling problems with general effects of learning and deterioration. Computers and Mathematics with Applications, 61, 100–108.

Yu, S., Ojiaku, J.-T., Wong, P. W.-H., & Xu, Y. (2012). Online makespan scheduling of linear deteriorating jobs on parallel machines. Lecture Notes in Computer Science, 7287, 260–272.

Yu, S., & Wong, P. W.-H. (2013). Online scheduling of simple linear deteriorating jobs to minimize the total general completion time. Theoretical Computer Science, 487, 95–102.

Zhang, X.-G., Wang, H., & Wang, X.-P. (2015). Patient scheduling problems with deferred deteriorated functions. Journal of Combinatorial Optimization, 30, 1027–1041.

Zhao, C.-L., & Tang, H.-Y. (2012). Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints. International Journal of Production Economics, 136, 131–136.

Zhao, C.-L., & Tang, H.-Y. (2014). Parallel machines scheduling with deteriorating jobs and availability constraints. Japan Journal of Industrial and Applied Mathematics, 31, 501–512.

Zou, J., Zhang, Y.-Z., & Miao, C.-X. (2013). Uniform parallel-machine scheduling with time dependent processing times. Journal of the Operational Research Society China, 1, 239–252.

Titel: A review of four decades of time-dependent scheduling: main results, new topics, and open problems
verfasst von: Stanisław Gawiejnowicz
Publikationsdatum: 28.01.2020
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 1/2020
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-019-00630-w

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2020

Approximation algorithms for the twin robot scheduling problem

Three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines

Journal of scheduling (2020)

Metaheuristics for solving a multi-objective flow shop scheduling problem with sequence-dependent setup times

Maximizing the number of jobs scheduled at their baseline starting times in case of machine failures

Minimizing the waiting time for a one-way shuttle service

Premium Partner