Skip to main content

2014 | OriginalPaper | Buchkapitel

4. Batching Scheduling Problems

verfasst von : Alessandro Agnetis, Jean-Charles Billaut, Stanisław Gawiejnowicz, Dario Pacciarelli, Ameur Soukhal

Erschienen in: Multiagent Scheduling

Verlag: Springer Berlin Heidelberg

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

search-config
loading …

Abstract

In this chapter, we consider batching scheduling problems in the context of agent scheduling. The main feature of these problems is the partition of the set of jobs into a number of subsets of jobs called batches. The chapter is composed of five sections. In Sect.4.1, we introduce basic definitions and notions of batching scheduling. In Sects. 4.2 and 4.3 we discuss two-agent s-batching and two-agent p-batching problems, respectively. We end the chapter with Sects. 4.4 and 4.5 including, respectively, complexity tables and bibliographic remarks.

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!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

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!

Literatur
Zurück zum Zitat Agnetis, A., Mirchandani, P., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52, 229–242. Agnetis, A., Mirchandani, P., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52, 229–242.
Zurück zum Zitat Agnetis, A., Pacciarelli, D., & Pacifici, A. (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150, 3–15. Agnetis, A., Pacciarelli, D., & Pacifici, A. (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150, 3–15.
Zurück zum Zitat Agnetis, A., de Pascale, G., & Pranzo, M. (2009a). Computing the nash solution for scheduling bargaining problems. International Journal of Operational Research, 1, 54–69. Agnetis, A., de Pascale, G., & Pranzo, M. (2009a). Computing the nash solution for scheduling bargaining problems. International Journal of Operational Research, 1, 54–69.
Zurück zum Zitat Agnetis, A., Pacciarelli, D., & de Pascale, G. (2009b). A Lagrangian approach to single-machine scheduling problems with two competing agents. Journal of Scheduling, 12, 401–415. Agnetis, A., Pacciarelli, D., & de Pascale, G. (2009b). A Lagrangian approach to single-machine scheduling problems with two competing agents. Journal of Scheduling, 12, 401–415.
Zurück zum Zitat Agnetis, A., Nicosia, G., Pacifici, A., & Pferschy, U. (2013). Two agents competing for a shared machine. Lecture Notes in Computer Science, 8176 LNAI, 1–14. Agnetis, A., Nicosia, G., Pacifici, A., & Pferschy, U. (2013). Two agents competing for a shared machine. Lecture Notes in Computer Science, 8176 LNAI, 1–14.
Zurück zum Zitat Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The design and analysis of computer algorithms. Reading: Addison-Wesley. Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The design and analysis of computer algorithms. Reading: Addison-Wesley.
Zurück zum Zitat Albers, S., & Brucker, P. (1993). The complexity of one-machine batching problems. Discrete Applied Mathematics, 47, 87–107. Albers, S., & Brucker, P. (1993). The complexity of one-machine batching problems. Discrete Applied Mathematics, 47, 87–107.
Zurück zum Zitat Alidaee, B., & Womer, N. K. (1999). Scheduling with time dependent processing times: Review and extensions. Journal of the Operatational Research Society, 50, 711–720. Alidaee, B., & Womer, N. K. (1999). Scheduling with time dependent processing times: Review and extensions. Journal of the Operatational Research Society, 50, 711–720.
Zurück zum Zitat Angel, E., Bampis, E., & Gourvès, L. (2005). Approximation results for a bicriteria job scheduling problem on a single machine without preemption. Information Processing Letters, 94, 19–27. Angel, E., Bampis, E., & Gourvès, L. (2005). Approximation results for a bicriteria job scheduling problem on a single machine without preemption. Information Processing Letters, 94, 19–27.
Zurück zum Zitat Anzanello, M. J., & Fogliatto, F. S. (2011). Learning curve models and applications: Literature review and research directions. International Journal of Industrial Ergonomics, 41, 573–583. Anzanello, M. J., & Fogliatto, F. S. (2011). Learning curve models and applications: Literature review and research directions. International Journal of Industrial Ergonomics, 41, 573–583.
Zurück zum Zitat Arbib, C., Flammini, M., & Marinelli, F. (2003). Minimum flow time graph ordering. Lecture Notes on Computer Science, 2880, 23–33. Arbib, C., Flammini, M., & Marinelli, F. (2003). Minimum flow time graph ordering. Lecture Notes on Computer Science, 2880, 23–33.
Zurück zum Zitat Bachman, A., & Janiak, A. (2000). Minimizing maximum lateness under linear deterioration. European Journal of Operational Research, 126, 557–566. Bachman, A., & Janiak, A. (2000). Minimizing maximum lateness under linear deterioration. European Journal of Operational Research, 126, 557–566.
Zurück zum Zitat Bachman, A., & Janiak, A. (2004). Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society, 55, 257–264. Bachman, A., & Janiak, A. (2004). Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society, 55, 257–264.
Zurück zum Zitat Baker, K., & Smith, J. C. (2003). A multiple criterion model for machine scheduling. Journal of Scheduling, 6, 7–16. Baker, K., & Smith, J. C. (2003). A multiple criterion model for machine scheduling. Journal of Scheduling, 6, 7–16.
Zurück zum Zitat Balasubramanian, H., Fowler, J., Keha, A., & Pfund, M. (2009). Scheduling interfering job sets on parallel machines. European Journal of Operational Research, 199, 55–67. Balasubramanian, H., Fowler, J., Keha, A., & Pfund, M. (2009). Scheduling interfering job sets on parallel machines. European Journal of Operational Research, 199, 55–67.
Zurück zum Zitat Bellman, R. (1957). Dynamic programming. Princeton: Princeton University Press. Bellman, R. (1957). Dynamic programming. Princeton: Princeton University Press.
Zurück zum Zitat Bellman, R., & Dreyfus, S. E. (1962). Applied dynamic programming. Princeton: Princeton University Press. Bellman, R., & Dreyfus, S. E. (1962). Applied dynamic programming. Princeton: Princeton University Press.
Zurück zum Zitat Biskup, D. (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188, 315–329. Biskup, D. (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188, 315–329.
Zurück zum Zitat Blazewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling: From theory to applications. Berlin/Heidelberg: Springer. Blazewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling: From theory to applications. Berlin/Heidelberg: Springer.
Zurück zum Zitat Bowman, E. H. (1959). The schedule sequencing problem. Operations Research, 7, 621–624. Bowman, E. H. (1959). The schedule sequencing problem. Operations Research, 7, 621–624.
Zurück zum Zitat Brewer, P. J., & Plott, C. R. (1996). A binary conflict ascending price (bicap) mechanism for the decentralized allocation of the right to use railroad tracks. International Journal of Industrial Organization, 14(6), 857–886. Brewer, P. J., & Plott, C. R. (1996). A binary conflict ascending price (bicap) mechanism for the decentralized allocation of the right to use railroad tracks. International Journal of Industrial Organization, 14(6), 857–886.
Zurück zum Zitat Brucker, P. (2007). Scheduling algorithms (5th ed.). Berlin: Springer. Brucker, P. (2007). Scheduling algorithms (5th ed.). Berlin: Springer.
Zurück zum Zitat Brucker, P., & Kovalyov, M. Y. (1996). Single machine batch scheduling to minimize the weighted number of late jobs. Mathematical Methods of Operations Research, 43, 1–8. Brucker, P., & Kovalyov, M. Y. (1996). Single machine batch scheduling to minimize the weighted number of late jobs. Mathematical Methods of Operations Research, 43, 1–8.
Zurück zum Zitat Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., & van de Velde, S. L. (1998). Scheduling a batching machine. Journal of Scheduling, 1(1), 31–54. Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., & van de Velde, S. L. (1998). Scheduling a batching machine. Journal of Scheduling, 1(1), 31–54.
Zurück zum Zitat Bruno, J., Coffman, E. G., & Sethi, R. (1974). Scheduling indepedant tasks to reduce mean finishing time. Communications of the ACM, 17, 382–387. Bruno, J., Coffman, E. G., & Sethi, R. (1974). Scheduling indepedant tasks to reduce mean finishing time. Communications of the ACM, 17, 382–387.
Zurück zum Zitat Chen, Z.-L. (1996). Parallel machine scheduling with time dependent processing times. Discrete Applied Mathematics, 70, 81–93. Chen, Z.-L. (1996). Parallel machine scheduling with time dependent processing times. Discrete Applied Mathematics, 70, 81–93.
Zurück zum Zitat Chen, Z.-L. (1997). Erratum to parallel machine scheduling with time dependent processing times. Discrete Applied Mathematics, 75, 103. Chen, Z.-L. (1997). Erratum to parallel machine scheduling with time dependent processing times. Discrete Applied Mathematics, 75, 103.
Zurück zum Zitat Chen, B., Potts, C. N., & Woeginger, G. J. (1998). A review of machine scheduling: Complexity and approximability. In D. Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization (pp. 21–169). Dordrecht: Kluwer Academic Publishers. Chen, B., Potts, C. N., & Woeginger, G. J. (1998). A review of machine scheduling: Complexity and approximability. In D. Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization (pp. 21–169). Dordrecht: Kluwer Academic Publishers.
Zurück zum Zitat Cheng, T. C. E., & Kovalyov, M. Y. (2001). Single machine batch scheduling with sequential job processing. IIE Transactions, 33, 413–420. Cheng, T. C. E., & Kovalyov, M. Y. (2001). Single machine batch scheduling with sequential job processing. IIE Transactions, 33, 413–420.
Zurück zum Zitat Cheng, T. C. E., Ding, Q., & Lin, B. (2004a). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152, 1–13. Cheng, T. C. E., Ding, Q., & Lin, B. (2004a). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152, 1–13.
Zurück zum Zitat Cheng, T. C. E., Kovalyov, M. Y., & Chakhlevich, K. N. (2004b). Batching in a two-stage flowshop with dedicated machines in the second stage. IIE Transactions, 36, 87–93. Cheng, T. C. E., Kovalyov, M. Y., & Chakhlevich, K. N. (2004b). Batching in a two-stage flowshop with dedicated machines in the second stage. IIE Transactions, 36, 87–93.
Zurück zum Zitat Cheng, T. C. E., Ng, C., & Yuan, J. J. (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 362, 273–281. Cheng, T. C. E., Ng, C., & Yuan, J. J. (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 362, 273–281.
Zurück zum Zitat Cheng, T. C. E., Ng, C., & Yuan, J. J. (2008). Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research, 188, 603–609. Cheng, T. C. E., Ng, C., & Yuan, J. J. (2008). Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research, 188, 603–609.
Zurück zum Zitat Cheng, T. C. E., Cheng, S. R., Wu, W., Hsu, P. H., & Wu, C. C. (2011a). A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations. Computers and Industrial Engineering, 60, 534–541. Cheng, T. C. E., Cheng, S. R., Wu, W., Hsu, P. H., & Wu, C. C. (2011a). A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations. Computers and Industrial Engineering, 60, 534–541.
Zurück zum Zitat Cheng, T. C. E., Wu, W., Cheng, S. R., & Wu, C. C. (2011b). Two-agent scheduling with position-based deteriorating jobs and learning effects. Applied Mathematics and Computation, 217, 8804–8824. Cheng, T. C. E., Wu, W., Cheng, S. R., & Wu, C. C. (2011b). Two-agent scheduling with position-based deteriorating jobs and learning effects. Applied Mathematics and Computation, 217, 8804–8824.
Zurück zum Zitat Cheng, T. C. E., Chung, Y.-H., Liao, S., & Lee, W.-C. (2013). Two-agent singe-machine scheduling with release times to minimize the total weighted completion time. Computers and Operations Research, 40, 353–361. Cheng, T. C. E., Chung, Y.-H., Liao, S., & Lee, W.-C. (2013). Two-agent singe-machine scheduling with release times to minimize the total weighted completion time. Computers and Operations Research, 40, 353–361.
Zurück zum Zitat Cho, Y., & Sahni, S. (1981). Preemptive scheduling of independent jobs with release and due times on open, flow and job shops. Operations Research, 29, 511–522. Cho, Y., & Sahni, S. (1981). Preemptive scheduling of independent jobs with release and due times on open, flow and job shops. Operations Research, 29, 511–522.
Zurück zum Zitat Choi, B., Leung, J.-T., & Pinedo, M. (2009). A note on the complexity of a two-agent, linear combination problem. Technical report, Stern School of Business at New York University, IOMS Department. Choi, B., Leung, J.-T., & Pinedo, M. (2009). A note on the complexity of a two-agent, linear combination problem. Technical report, Stern School of Business at New York University, IOMS Department.
Zurück zum Zitat Coffman, E. G., Yannakakis, J. M., Magazine, M. J., & Santos, C. A. (1990). Batch sizing and job sequencing on a single machine. Annals of Operations Research, 26, 135–147. Coffman, E. G., Yannakakis, J. M., Magazine, M. J., & Santos, C. A. (1990). Batch sizing and job sequencing on a single machine. Annals of Operations Research, 26, 135–147.
Zurück zum Zitat Conway, R., Maxwell, W., & Miller, L. (1967). Theory of scheduling. Reading: Addison-Wesley Conway, R., Maxwell, W., & Miller, L. (1967). Theory of scheduling. Reading: Addison-Wesley
Zurück zum Zitat Cook, S. A. (1971). The complexity of theorem proving procedures. In Third annual ACM symposium on theory of computing (STOC ’71), Shaker Heights (pp. 151–158). New York: ACM Cook, S. A. (1971). The complexity of theorem proving procedures. In Third annual ACM symposium on theory of computing (STOC ’71), Shaker Heights (pp. 151–158). New York: ACM
Zurück zum Zitat Cormen, T. H., Leiserson, C. E., & Rivest, R. L. (1994). Introduction to algorithms. Cambridge: MIT. Cormen, T. H., Leiserson, C. E., & Rivest, R. L. (1994). Introduction to algorithms. Cambridge: MIT.
Zurück zum Zitat Dessouky, M. I., Lageweg, B. J., Lenstra, J. K., & van de Velde, S. L. (1990). Scheduling identical jobs on uniform parallel machines. Statistica Neerlandica, 44, 115–123. Dessouky, M. I., Lageweg, B. J., Lenstra, J. K., & van de Velde, S. L. (1990). Scheduling identical jobs on uniform parallel machines. Statistica Neerlandica, 44, 115–123.
Zurück zum Zitat Dileepan, P., & Sen, T. (1988). Bicriterion static scheduling research for a single machine. Omega. The International Journal of Management Science, 16, 53–59. Dileepan, P., & Sen, T. (1988). Bicriterion static scheduling research for a single machine. Omega. The International Journal of Management Science, 16, 53–59.
Zurück zum Zitat Ding, G., & Sun, S. (2010). Single-machine scheduling problems with two agents competing for makespan. Lecture Notes in Computer Science, 6328, 244–255. Ding, G., & Sun, S. (2010). Single-machine scheduling problems with two agents competing for makespan. Lecture Notes in Computer Science, 6328, 244–255.
Zurück zum Zitat Du, J., & Leung, J. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of operations research, 15, 483–495. Du, J., & Leung, J. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of operations research, 15, 483–495.
Zurück zum Zitat Ehrgott, M., Shao, L., & Schobel, A. (2011). An approximation algorithm for convex multi-objective programming problems. Journal of Global Optimization, 50, 397–416. Ehrgott, M., Shao, L., & Schobel, A. (2011). An approximation algorithm for convex multi-objective programming problems. Journal of Global Optimization, 50, 397–416.
Zurück zum Zitat Elvikis, D., Hamacher, H. W., & T’Kindt, V. (2011). Scheduling two agents on uniform parallel machines with makespan and cost functions. Journal of Scheduling, 14, 471–481. Elvikis, D., Hamacher, H. W., & T’Kindt, V. (2011). Scheduling two agents on uniform parallel machines with makespan and cost functions. Journal of Scheduling, 14, 471–481.
Zurück zum Zitat Fan, B., Cheng, T., Li, S., & Feng, Q. (2013). Bounded parallel-batching scheduling with two competing agents. Journal of Scheduling, 16, 261–271. Fan, B., Cheng, T., Li, S., & Feng, Q. (2013). Bounded parallel-batching scheduling with two competing agents. Journal of Scheduling, 16, 261–271.
Zurück zum Zitat Feng, Q., Yu, Z., & Shang, W. (2011). Pareto optimization of serial-batching scheduling problems on two agents. In 2011 international conference on advanced mechatronic systems (ICAMechS) (pp. 165–168). ISBN 978-1-4577-1698-0. Feng, Q., Yu, Z., & Shang, W. (2011). Pareto optimization of serial-batching scheduling problems on two agents. In 2011 international conference on advanced mechatronic systems (ICAMechS) (pp. 165–168). ISBN 978-1-4577-1698-0.
Zurück zum Zitat Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of \(\mathcal{N}\mathcal{P}\) -completeness. New York: W.H. Freeman and Company. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of \(\mathcal{N}\mathcal{P}\) -completeness. New York: W.H. Freeman and Company.
Zurück zum Zitat Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117–129. Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117–129.
Zurück zum Zitat Gavranovic, H., & Finke, G. (2000). Graph partitioning and set covering for optimal design of production system in the metal industry. In The second conference on management and control of production and logistics – MCPL’00, Grenoble. Gavranovic, H., & Finke, G. (2000). Graph partitioning and set covering for optimal design of production system in the metal industry. In The second conference on management and control of production and logistics – MCPL’00, Grenoble.
Zurück zum Zitat Gawiejnowicz, S. (1996). Brief survey of continuous models of scheduling. Foundations of Computing and Decision Sciences, 21, 81–100. Gawiejnowicz, S. (1996). Brief survey of continuous models of scheduling. Foundations of Computing and Decision Sciences, 21, 81–100.
Zurück zum Zitat Gawiejnowicz, S. (2008). Time-dependent scheduling: EATCS monographs in theoretical computer science. Berlin/New York: Springer. Gawiejnowicz, S. (2008). Time-dependent scheduling: EATCS monographs in theoretical computer science. Berlin/New York: Springer.
Zurück zum Zitat Gawiejnowicz, S., & Kononov, A. (2012, in press). Isomorphic scheduling problems. Annals of Operations Research. doi:10.1007/s10479-012-1222-2. Gawiejnowicz, S., & Kononov, A. (2012, in press). Isomorphic scheduling problems. Annals of Operations Research. doi:10.1007/s10479-012-1222-2.
Zurück zum Zitat Gawiejnowicz, S., Onak, T., & Suwalski, C. (2006). A new library for evolutionary algorithms. Lecture Notes in Computer Science, 3911, 414–421. Gawiejnowicz, S., Onak, T., & Suwalski, C. (2006). A new library for evolutionary algorithms. Lecture Notes in Computer Science, 3911, 414–421.
Zurück zum Zitat Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2009a). Conjugate problems in time-dependent scheduling. Journal of Scheduling, 12, 543–553. Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2009a). Conjugate problems in time-dependent scheduling. Journal of Scheduling, 12, 543–553.
Zurück zum Zitat Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2009b). Equivalent time-dependent scheduling problems. European Journal of Operational Research, 196, 919–929. Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2009b). Equivalent time-dependent scheduling problems. European Journal of Operational Research, 196, 919–929.
Zurück zum Zitat Gawiejnowicz, S., Lee, W. C., Lin, C. L., & Wu, C. C. (2011). Single-machine scheduling of proportionally deteriorating jobs by two agents. Journal of the Operational Research Society, 62, 1983–1991. Gawiejnowicz, S., Lee, W. C., Lin, C. L., & Wu, C. C. (2011). Single-machine scheduling of proportionally deteriorating jobs by two agents. Journal of the Operational Research Society, 62, 1983–1991.
Zurück zum Zitat Geoffrion, A. M. (1968). Proper efficiency and the theory of vector maximization. Journal of Mathematical Analysis and Applications, 22, 618–630. Geoffrion, A. M. (1968). Proper efficiency and the theory of vector maximization. Journal of Mathematical Analysis and Applications, 22, 618–630.
Zurück zum Zitat Geoffrion, A. M. (1974). Lagrangian relaxation for integer programming. Mathematical Programming Study, 2, 82–114. Geoffrion, A. M. (1974). Lagrangian relaxation for integer programming. Mathematical Programming Study, 2, 82–114.
Zurück zum Zitat Graham, R. L. (1966). Bounds for certain multiprocessor anomalies. Bell System Technical Journals, 17, 1563–1581. Graham, R. L. (1966). Bounds for certain multiprocessor anomalies. Bell System Technical Journals, 17, 1563–1581.
Zurück zum Zitat 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. 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.
Zurück zum Zitat He, C., Lin, Y., & Yuan, J. (2007). Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theoretical Computer Science, 381, 234–240. He, C., Lin, Y., & Yuan, J. (2007). Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. Theoretical Computer Science, 381, 234–240.
Zurück zum Zitat Hochbaum, D. (1998). Approximation algorithms for NP-hard problems. Boston: PWS Publishing. Hochbaum, D. (1998). Approximation algorithms for NP-hard problems. Boston: PWS Publishing.
Zurück zum Zitat Hochbaum, D. S., & Landy, D. (1994). Scheduling with batching: Minimizing the weighted number of tardy jobs. Operations Research Letters, 16, 79–86. Hochbaum, D. S., & Landy, D. (1994). Scheduling with batching: Minimizing the weighted number of tardy jobs. Operations Research Letters, 16, 79–86.
Zurück zum Zitat Hoogeveen, J. A. (1996). Single-machine scheduling to minimize a function of two or three maximum cost criteria. Journal of Algorithms, 21, 415–433. Hoogeveen, J. A. (1996). Single-machine scheduling to minimize a function of two or three maximum cost criteria. Journal of Algorithms, 21, 415–433.
Zurück zum Zitat Hoogeveen, H. (2005). Multicriteria scheduling. European Journal of Operational Research, 167, 592–623. Hoogeveen, H. (2005). Multicriteria scheduling. European Journal of Operational Research, 167, 592–623.
Zurück zum Zitat Hoogeveen, J. A., & van de Velde, S. L. (1995). Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time. Operations Research Letters, 17, 205–208. Hoogeveen, J. A., & van de Velde, S. L. (1995). Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time. Operations Research Letters, 17, 205–208.
Zurück zum Zitat Hopcroft, J. E., & Karp, R. M. (1973). An \({n}^{frac52}\) algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 4, 225–231. Hopcroft, J. E., & Karp, R. M. (1973). An \({n}^{frac52}\) algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 4, 225–231.
Zurück zum Zitat Hopcroft, J., & Ullman, J. (1979). Introduction to automata theory, languages and computation. Reading: Addison-Wesley. Hopcroft, J., & Ullman, J. (1979). Introduction to automata theory, languages and computation. Reading: Addison-Wesley.
Zurück zum Zitat Horn, W. A. (1973). Minimizing average flow time with parallel machines. Operations Research, 21, 846–847. Horn, W. A. (1973). Minimizing average flow time with parallel machines. Operations Research, 21, 846–847.
Zurück zum Zitat Huo, Y., Leung, J. Y.-T., & Zhao, H. (2007a). Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness. European Journal of Operational Research, 177, 116–134. Huo, Y., Leung, J. Y.-T., & Zhao, H. (2007a). Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness. European Journal of Operational Research, 177, 116–134.
Zurück zum Zitat Huo, Y., Leung, J. Y.-T., & Zhao, H. (2007b). Complexity of two dual criteria scheduling problems. Operations Research Letters, 35, 211–220. Huo, Y., Leung, J. Y.-T., & Zhao, H. (2007b). Complexity of two dual criteria scheduling problems. Operations Research Letters, 35, 211–220.
Zurück zum Zitat Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness. In Management Science Research (Vol. 43). Los Angeles: University of California. Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness. In Management Science Research (Vol. 43). Los Angeles: University of California.
Zurück zum Zitat Johnson, S. M. (1954). Optimal two and three-stage production schedules with setup times included. Naval Research Logistic Quarterly, 1, 61–67. Johnson, S. M. (1954). Optimal two and three-stage production schedules with setup times included. Naval Research Logistic Quarterly, 1, 61–67.
Zurück zum Zitat Johnson, D. (1982). The NP-completeness column: An ongoing guide. Journal of Algorithms, 2, 393–405. Johnson, D. (1982). The NP-completeness column: An ongoing guide. Journal of Algorithms, 2, 393–405.
Zurück zum Zitat Johnson, D. S. (1990). A catalog of complexity classes. In J. van Leeuwen (Ed.), Handbook of theoretical computer science: Algorithms and complexity (pp. 67–161). Elsevier/MIT: Amsterdam/Cambridge. Johnson, D. S. (1990). A catalog of complexity classes. In J. van Leeuwen (Ed.), Handbook of theoretical computer science: Algorithms and complexity (pp. 67–161). Elsevier/MIT: Amsterdam/Cambridge.
Zurück zum Zitat Jozefowska, J. (2007). Just-in-time scheduling: Models and algorithms for computer and manufacturing systems. Berlin: Springer. Jozefowska, J. (2007). Just-in-time scheduling: Models and algorithms for computer and manufacturing systems. Berlin: Springer.
Zurück zum Zitat Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–104). New York: Plenum Press. Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85–104). New York: Plenum Press.
Zurück zum Zitat Kellerer, H., & Strusevich, V. A. (2010). Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica, 57, 769–795. Kellerer, H., & Strusevich, V. A. (2010). Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica, 57, 769–795.
Zurück zum Zitat Khowala, K., Fowler, J., Keha, A., & Balasubramanian, H. (2009). Single machine scheduling with interfering job sets. In Multidisciplinary international conference on scheduling: Theory and applications (MISTA 2009), 10–12 Aug 2009, Dublin (pp. 357–365). Khowala, K., Fowler, J., Keha, A., & Balasubramanian, H. (2009). Single machine scheduling with interfering job sets. In Multidisciplinary international conference on scheduling: Theory and applications (MISTA 2009), 10–12 Aug 2009, Dublin (pp. 357–365).
Zurück zum Zitat Knotts, G., Dror, M., & Hartman, B. C. (2000). Agent-based project scheduling. IIE Transactions, 32, 387–401. Knotts, G., Dror, M., & Hartman, B. C. (2000). Agent-based project scheduling. IIE Transactions, 32, 387–401.
Zurück zum Zitat Knuth, D. E. (1967–1969). The art of computer programming (Vols. 1–3). Reading: Addison-Wesley. Knuth, D. E. (1967–1969). The art of computer programming (Vols. 1–3). Reading: Addison-Wesley.
Zurück zum Zitat Kononov, A. (1997). Scheduling problems with linear increasing processing times. In Operations research September 3–6, 1996, Braunschweig (pp. 208–212). Springer. Kononov, A. (1997). Scheduling problems with linear increasing processing times. In Operations research September 3–6, 1996, Braunschweig (pp. 208–212). Springer.
Zurück zum Zitat Kononov, A. (1998). Single machine scheduling problems with processing times proportional to an arbitrary function. Discrete Analysis and Operations Research, 5, 17–37. Kononov, A. (1998). Single machine scheduling problems with processing times proportional to an arbitrary function. Discrete Analysis and Operations Research, 5, 17–37.
Zurück zum Zitat Kononov, A., & Gawiejnowicz, S. (2001). NP-hard cases in scheduling deteriorating jobs on dedicated machines. Journal of the Operational Research Society, 52, 708–718. Kononov, A., & Gawiejnowicz, S. (2001). NP-hard cases in scheduling deteriorating jobs on dedicated machines. Journal of the Operational Research Society, 52, 708–718.
Zurück zum Zitat Kovalyov, M. Y., Oulamara, A., & Soukhal, A. (2012). Two-agent scheduling on an unbounded serial batching machine. Lecture Notes in Computer Science, 7422 LNCS, 427–438. Kovalyov, M. Y., Oulamara, A., & Soukhal, A. (2012). Two-agent scheduling on an unbounded serial batching machine. Lecture Notes in Computer Science, 7422 LNCS, 427–438.
Zurück zum Zitat Kovalyov, M. Y., Oulamara, A., & Soukhal, A. (2012b). Two-agent scheduling with agent specific batches on an unbounded serial batching machine. In The 2nd international symposium on combinatorial optimization, ISCO 2012: Vol. 7422. Lecture Notes in Computer Science, Athens. Kovalyov, M. Y., Oulamara, A., & Soukhal, A. (2012b). Two-agent scheduling with agent specific batches on an unbounded serial batching machine. In The 2nd international symposium on combinatorial optimization, ISCO 2012: Vol. 7422. Lecture Notes in Computer Science, Athens.
Zurück zum Zitat Laumanns, M., Thiele, L., & Zitzler, E. (2006). An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal of Operational Research, 169(3), 932–942. Laumanns, M., Thiele, L., & Zitzler, E. (2006). An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal of Operational Research, 169(3), 932–942.
Zurück zum Zitat Lawler, E. L. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19(8), 544–546. Lawler, E. L. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19(8), 544–546.
Zurück zum Zitat Lawler, E. L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342. Lawler, E. L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342.
Zurück zum Zitat Lawler, E. L. (1982). Scheduling a single machine to minimize the number of late jobs (Vol. 1, pp. 331–342). Berkeley: Computer Science Division, University of California. (preprint) Lawler, E. L. (1982). Scheduling a single machine to minimize the number of late jobs (Vol. 1, pp. 331–342). Berkeley: Computer Science Division, University of California. (preprint)
Zurück zum Zitat Lawler, E. L. (1990). A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Annals of Operations Research, 26, 125–133. Lawler, E. L. (1990). A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Annals of Operations Research, 26, 125–133.
Zurück zum Zitat Lawler, E. L., & Moore, J. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77–84. Lawler, E. L., & Moore, J. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77–84.
Zurück zum Zitat Lee, C. (1991). Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics, 20, 53–61. Lee, C. (1991). Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics, 20, 53–61.
Zurück zum Zitat Lee, C. Y., & Vairaktarakis, G. (1993). Complexity of single machine hierarchical scheduling: A survey. In P. M. Pardalos (Ed.), Complexity in numerical optimization (pp. 269–298). Singapore: World Scientific. Lee, C. Y., & Vairaktarakis, G. (1993). Complexity of single machine hierarchical scheduling: A survey. In P. M. Pardalos (Ed.), Complexity in numerical optimization (pp. 269–298). Singapore: World Scientific.
Zurück zum Zitat Lee, K., Choi, B.-C., Leung, J. Y.-T., & Pinedo, M. L. (2009). Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Information Processing Letters, 109, 913–917. Lee, K., Choi, B.-C., Leung, J. Y.-T., & Pinedo, M. L. (2009). Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Information Processing Letters, 109, 913–917.
Zurück zum Zitat Lee, W. C., Wang, W. J., Shiau, Y. R., & Wu, C. C. (2010). A single-machine scheduling problem with two-agent and deteriorating jobs. Applied Mathematical Modelling, 34(10), 3098–3107. Lee, W. C., Wang, W. J., Shiau, Y. R., & Wu, C. C. (2010). A single-machine scheduling problem with two-agent and deteriorating jobs. Applied Mathematical Modelling, 34(10), 3098–3107.
Zurück zum Zitat Lee, W. C., Chung, Y., & Hu, M. (2012). Genetic algorithms for a two-agent single-machine problem with release time. Applied Soft Computing, 12, 3580–3589. Lee, W. C., Chung, Y., & Hu, M. (2012). Genetic algorithms for a two-agent single-machine problem with release time. Applied Soft Computing, 12, 3580–3589.
Zurück zum Zitat Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362. Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.
Zurück zum Zitat Leung, J. Y.-T., & Young, G. H. (1989). Minimizing schedule length subject to minimum flow time. SIAM Journal on Computing, 18(2), 314–326. Leung, J. Y.-T., & Young, G. H. (1989). Minimizing schedule length subject to minimum flow time. SIAM Journal on Computing, 18(2), 314–326.
Zurück zum Zitat Leung, J. Y.-T., Yu, V. K. M., & Wei, W.-D. (1994). Minimizing the weighted number of tardy task units. Discrete Applied Mathematics, 51, 307–316. Leung, J. Y.-T., Yu, V. K. M., & Wei, W.-D. (1994). Minimizing the weighted number of tardy task units. Discrete Applied Mathematics, 51, 307–316.
Zurück zum Zitat Leung, J. Y.-T., Pinedo, M. L., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458–469. Leung, J. Y.-T., Pinedo, M. L., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458–469.
Zurück zum Zitat Levin, A., & Woeginger, G. J. (2006). The constrained minimum weighted sum of job completion times problem. Mathematical Programming Series A, 108, 115–126. Levin, A., & Woeginger, G. J. (2006). The constrained minimum weighted sum of job completion times problem. Mathematical Programming Series A, 108, 115–126.
Zurück zum Zitat Lew, A., & Mauch, H. (2007). Dynamic programming: A computational tool. Berlin/Heidelberg: Springer. Lew, A., & Mauch, H. (2007). Dynamic programming: A computational tool. Berlin/Heidelberg: Springer.
Zurück zum Zitat Lewis, H. R., & Papadimitriou, C. H. (1998). Elements of the theory of computation (2nd ed.). Upper Saddle River: Prentice-Hall. Lewis, H. R., & Papadimitriou, C. H. (1998). Elements of the theory of computation (2nd ed.). Upper Saddle River: Prentice-Hall.
Zurück zum Zitat Li, D. C., & Hsu, P. H. (2012). Solving a two-agent single-machine scheduling problem considering learning effect. Computers and Operations Research, 39, 1644–1651. Li, D. C., & Hsu, P. H. (2012). Solving a two-agent single-machine scheduling problem considering learning effect. Computers and Operations Research, 39, 1644–1651.
Zurück zum Zitat Li, S., & Yuan, J. (2012). Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 15, 629–640. Li, S., & Yuan, J. (2012). Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 15, 629–640.
Zurück zum Zitat 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. (2008). Two-agent scheduling with linear deteriorating jobs on a single machine. Lecture Notes in Computer Science, 5092, 642–650.
Zurück zum Zitat Liu, P., Tang, L., & Zhou, X. (2010a). Two-agent group scheduling with deteriorating jobs on a single machine. International Journal of Advanced Manufacturing Technology, 47, 657–664. Liu, P., Tang, L., & Zhou, X. (2010a). Two-agent group scheduling with deteriorating jobs on a single machine. International Journal of Advanced Manufacturing Technology, 47, 657–664.
Zurück zum Zitat Liu, P., Zhou, X., & Tang, L. (2010b). Two-agent group single-machine scheduling with position-dependent processing times. International Journal of Advanced Manufacturing Technology, 48, 325–331. Liu, P., Zhou, X., & Tang, L. (2010b). Two-agent group single-machine scheduling with position-dependent processing times. International Journal of Advanced Manufacturing Technology, 48, 325–331.
Zurück zum Zitat Liu, P., Yi, N., & Zhou, X. Y. (2011). Two-agent single-machine scheduling problems under increasing linear deterioration. Applied Mathematical Modelling, 35, 2290–2296. Liu, P., Yi, N., & Zhou, X. Y. (2011). Two-agent single-machine scheduling problems under increasing linear deterioration. Applied Mathematical Modelling, 35, 2290–2296.
Zurück zum Zitat Liu, P., Yi, N., Zhou, X., & Gong, H. (2013). Scheduling two agents with sum-of-processing-times-based deterioration on a single machine. Applied Mathematics and Computation, 219, 8848–8855. Liu, P., Yi, N., Zhou, X., & Gong, H. (2013). Scheduling two agents with sum-of-processing-times-based deterioration on a single machine. Applied Mathematics and Computation, 219, 8848–8855.
Zurück zum Zitat Manne, A. S. (1960). On the job-shop scheduling problem. Operations Research, 8, 219–223. Manne, A. S. (1960). On the job-shop scheduling problem. Operations Research, 8, 219–223.
Zurück zum Zitat Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in multi-objective mathematical programming problems. Applied Mathematics and Computation, 213(2), 455–465. Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in multi-objective mathematical programming problems. Applied Mathematics and Computation, 213(2), 455–465.
Zurück zum Zitat Mc Naughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 6, 1–12. Mc Naughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 6, 1–12.
Zurück zum Zitat Meiners, C. R., & Torng, E. (2007). Mixed criteria packet scheduling. In M. Y. Kao & X.-Y. Li (Eds.), AAIM 2007: Vol. 4508. Lecture Notes on Computer Science (pp. 120–133). Berlin/Heidelberg: Springer. Meiners, C. R., & Torng, E. (2007). Mixed criteria packet scheduling. In M. Y. Kao & X.-Y. Li (Eds.), AAIM 2007: Vol. 4508. Lecture Notes on Computer Science (pp. 120–133). Berlin/Heidelberg: Springer.
Zurück zum Zitat Mohri, S., Masuda, T., & Ishii, H. (1999). Bi-criteria scheduling problem on three identical parallel machines. International Journal of Production Economics, 60–61, 529–536. Mohri, S., Masuda, T., & Ishii, H. (1999). Bi-criteria scheduling problem on three identical parallel machines. International Journal of Production Economics, 60–61, 529–536.
Zurück zum Zitat Moore, J. M. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15, 102–109. Moore, J. M. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15, 102–109.
Zurück zum Zitat Mor, B., & Mosheiov, G. (2010). Scheduling problems with two competing agents to minimize minmax and minsum earliness measures. European Journal of Operational Research, 206(3), 540–546. Mor, B., & Mosheiov, G. (2010). Scheduling problems with two competing agents to minimize minmax and minsum earliness measures. European Journal of Operational Research, 206(3), 540–546.
Zurück zum Zitat Mor, B., & Mosheiov, G. (2011). Single machine batch scheduling with two competing agents to minimize total flowtime. European Journal of Operational Research, 215(3), 524–531. Mor, B., & Mosheiov, G. (2011). Single machine batch scheduling with two competing agents to minimize total flowtime. European Journal of Operational Research, 215(3), 524–531.
Zurück zum Zitat Mosheiov, G. (1994). Scheduling jobs under simple linear deterioration. Computers and Operations Research, 21, 653–659. Mosheiov, G. (1994). Scheduling jobs under simple linear deterioration. Computers and Operations Research, 21, 653–659.
Zurück zum Zitat Mosheiov, G. (2002). Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete Applied Mathematics, 117, 195–209. Mosheiov, G. (2002). Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete Applied Mathematics, 117, 195–209.
Zurück zum Zitat Nagar, A., Haddock, J., & Heragu, S. (1995). Multiple and bicriteria scheduling: A literature survey. European Journal of the Operational Research, 81, 88–104. Nagar, A., Haddock, J., & Heragu, S. (1995). Multiple and bicriteria scheduling: A literature survey. European Journal of the Operational Research, 81, 88–104.
Zurück zum Zitat Ng, C. T., Cheng, T. C. E., & Yuan, J. J. (2006). A note on the complexity of the problem of two-agent scheduling on a single machine. Journal of Combinatorial Optimization, 12, 387–394. Ng, C. T., Cheng, T. C. E., & Yuan, J. J. (2006). A note on the complexity of the problem of two-agent scheduling on a single machine. Journal of Combinatorial Optimization, 12, 387–394.
Zurück zum Zitat Nong, Q., Ng, C., & Cheng, T. (2008). The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan. Operations Research Letters, 36(1), 61–66. Nong, Q., Ng, C., & Cheng, T. (2008). The bounded single-machine parallel-batching scheduling problem with family jobs and release dates to minimize makespan. Operations Research Letters, 36(1), 61–66.
Zurück zum Zitat Nong, Q., Cheng, T., & Ng, C. (2011). Two-agent scheduling to minimize the total cost. European Journal of Operational Research, 215, 39–44. Nong, Q., Cheng, T., & Ng, C. (2011). Two-agent scheduling to minimize the total cost. European Journal of Operational Research, 215, 39–44.
Zurück zum Zitat Nowicki, E., & Zdrzalka, S. (1990). A survey of results for sequencing problems with controllable processing times. Discrete Applied Mathematics, 26, 271–287. Nowicki, E., & Zdrzalka, S. (1990). A survey of results for sequencing problems with controllable processing times. Discrete Applied Mathematics, 26, 271–287.
Zurück zum Zitat Oulamara, A., Kovalyov, M. Y., & Finke, G. (2005). Scheduling a no-wait flowshop with unbounded batching machines. IIE Transactions on Scheduling and Logistics, 37, 685–696. Oulamara, A., Kovalyov, M. Y., & Finke, G. (2005). Scheduling a no-wait flowshop with unbounded batching machines. IIE Transactions on Scheduling and Logistics, 37, 685–696.
Zurück zum Zitat Oulamara, A., Finke, G., & Kuiten, A. K. (2009). Flowshop scheduling problem with batching machine and task compatibilities. Computers & Operations Research, 36, 391–401. Oulamara, A., Finke, G., & Kuiten, A. K. (2009). Flowshop scheduling problem with batching machine and task compatibilities. Computers & Operations Research, 36, 391–401.
Zurück zum Zitat Papadimitriou, C. M. (1994). Computational complexity. Reading: Addison Wesley. Papadimitriou, C. M. (1994). Computational complexity. Reading: Addison Wesley.
Zurück zum Zitat Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial optimization: Algorithms and complexity. Englewood Cliffs: Prentice-Hall. Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial optimization: Algorithms and complexity. Englewood Cliffs: Prentice-Hall.
Zurück zum Zitat Peha, J. M. (1995). Heterogeneous-criteria scheduling: Minimizing weighted number of tardy jobs and weighted completion time. Journal of Computers and Operations Research, 22, 1089–1100. Peha, J. M. (1995). Heterogeneous-criteria scheduling: Minimizing weighted number of tardy jobs and weighted completion time. Journal of Computers and Operations Research, 22, 1089–1100.
Zurück zum Zitat Pessan, C., Bouquard, J.-L., & Neron, E. (2008). An unrelated parallelmachines model for an industrial production resetting problem. European Journal of Industrial Engineering, 2, 153–171. Pessan, C., Bouquard, J.-L., & Neron, E. (2008). An unrelated parallelmachines model for an industrial production resetting problem. European Journal of Industrial Engineering, 2, 153–171.
Zurück zum Zitat Pinedo, M. (2008). Scheduling: Theory, algorithms, and systems (3rd ed.). Berlin: Springer. Pinedo, M. (2008). Scheduling: Theory, algorithms, and systems (3rd ed.). Berlin: Springer.
Zurück zum Zitat Potts, C., & Kovalyov, M. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120(2), 228–249. Potts, C., & Kovalyov, M. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120(2), 228–249.
Zurück zum Zitat Potts, C., Strusevich, V., & Tautenhahn, T. (2001). Scheduling batches with simultaneous job processing for two-machine shop problems. Journal of Scheduling, 4(1), 25–51. Potts, C., Strusevich, V., & Tautenhahn, T. (2001). Scheduling batches with simultaneous job processing for two-machine shop problems. Journal of Scheduling, 4(1), 25–51.
Zurück zum Zitat Qi, F., Yuan, J. J., Liu, H., & He, C. (2013). A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives. Applied Mathematical Modelling, 37, 7071–7076. Qi, F., Yuan, J. J., Liu, H., & He, C. (2013). A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives. Applied Mathematical Modelling, 37, 7071–7076.
Zurück zum Zitat Queyranne, M. (1993). Structure of a simple scheduling polyhedron. Mathematical Programming, 58, 263–285. Queyranne, M. (1993). Structure of a simple scheduling polyhedron. Mathematical Programming, 58, 263–285.
Zurück zum Zitat Rustogi, K., & Strusevich, V. A. (2012). Simple matching vs linear assignment in scheduling models with positional effects: A critical review. European Journal of Operational Research, 222, 393–407. Rustogi, K., & Strusevich, V. A. (2012). Simple matching vs linear assignment in scheduling models with positional effects: A critical review. European Journal of Operational Research, 222, 393–407.
Zurück zum Zitat Ruzika, S., & Wiecek, M. M. (2005). Approximation methods in multiobjective programming. Journal of Optimization Theory and Applications, 126(3), 473–501. Ruzika, S., & Wiecek, M. M. (2005). Approximation methods in multiobjective programming. Journal of Optimization Theory and Applications, 126(3), 473–501.
Zurück zum Zitat Sabouni, M. Y., & Jolai, F. (2010). Optimal methods for batch processing problem with makespan and maximum lateness objectives. Applied Mathematical Modelling, 34(2), 314–324. Sabouni, M. Y., & Jolai, F. (2010). Optimal methods for batch processing problem with makespan and maximum lateness objectives. Applied Mathematical Modelling, 34(2), 314–324.
Zurück zum Zitat Sadi, F., Soukhal, A., & Billaut, J.-C. (2013, to appear). Solving multi-agent scheduling problems on parallel machines with a global objective function. RAIRO Operations Research. Sadi, F., Soukhal, A., & Billaut, J.-C. (2013, to appear). Solving multi-agent scheduling problems on parallel machines with a global objective function. RAIRO Operations Research.
Zurück zum Zitat Saule, E., & Trystram, D. (2009). Multi-users scheduling in parallel systems. In Proceedings of the 23rd international symposium on parallel & distributed computing 2009, Rome (pp. 1–9). IEEE Computer Society. Saule, E., & Trystram, D. (2009). Multi-users scheduling in parallel systems. In Proceedings of the 23rd international symposium on parallel & distributed computing 2009, Rome (pp. 1–9). IEEE Computer Society.
Zurück zum Zitat Schuurman, P., & Woeginger, G. J. (2011). Approximation schemes – A tutorial. In R. H. Mohring, C. N. Potts, A. S. Schulz, G. J. Woeginger, & L. A. Wolsey (Eds.), Lectures on scheduling. Schuurman, P., & Woeginger, G. J. (2011). Approximation schemes – A tutorial. In R. H. Mohring, C. N. Potts, A. S. Schulz, G. J. Woeginger, & L. A. Wolsey (Eds.), Lectures on scheduling.
Zurück zum Zitat Sedeño-Noda, A., Alcaide, D., & González-Martín, C. (2006). Network flow approaches to pre-emptive open-shop scheduling problems with time-windows. European Journal of Operational Research, 174(3), 1501–1518. Sedeño-Noda, A., Alcaide, D., & González-Martín, C. (2006). Network flow approaches to pre-emptive open-shop scheduling problems with time-windows. European Journal of Operational Research, 174(3), 1501–1518.
Zurück zum Zitat Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643–1666. Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643–1666.
Zurück zum Zitat Smith, W. E. (1956). Various optimizer for single-stage production. Naval Research Logistics Quarterly, 3, 59–66. Smith, W. E. (1956). Various optimizer for single-stage production. Naval Research Logistics Quarterly, 3, 59–66.
Zurück zum Zitat Su, L.-H. (2009). Scheduling on identical parallel machines to minimize total completion time with deadline and machine eligibility constraints. The International Journal of Advanced Manufacturing Technology, 40, 572–581. Su, L.-H. (2009). Scheduling on identical parallel machines to minimize total completion time with deadline and machine eligibility constraints. The International Journal of Advanced Manufacturing Technology, 40, 572–581.
Zurück zum Zitat Tan, Q., Chen, H.-P., Du, B., & Li, X.-L. (2011). Two-agent scheduling on a single batch processing machine with non-identical job sizes. In Proceedings of the 2nd international conference on artificial intelligence, management science and electronic commerce, AIMSEC 2011, Art. No. 6009883 (pp. 7431–7435). Tan, Q., Chen, H.-P., Du, B., & Li, X.-L. (2011). Two-agent scheduling on a single batch processing machine with non-identical job sizes. In Proceedings of the 2nd international conference on artificial intelligence, management science and electronic commerce, AIMSEC 2011, Art. No. 6009883 (pp. 7431–7435).
Zurück zum Zitat T’kindt, D. E. V. (2012, in press). Two-agent scheduling on uniform parallel machines with min-max criteria. Annals of Operations Research, 1–16. T’kindt, D. E. V. (2012, in press). Two-agent scheduling on uniform parallel machines with min-max criteria. Annals of Operations Research, 1–16.
Zurück zum Zitat T’Kindt, V., & Billaut, J.-C. (2006). Multicriteria scheduling: Theory, models and algorithms (2nd ed.). Berlin/Heildelberg/New York: Springer. T’Kindt, V., & Billaut, J.-C. (2006). Multicriteria scheduling: Theory, models and algorithms (2nd ed.). Berlin/Heildelberg/New York: Springer.
Zurück zum Zitat Tuong, N. H. (2009). Complexité et Algorithmes pour l’Ordonnancement Multicritere de Travaux Indépendants: Problèmes Juste-À-Temps et Travaux Interférants (in French). PhD thesis, Université François-Rabelais de Tours, Tours. Tuong, N. H. (2009). Complexité et Algorithmes pour l’Ordonnancement Multicritere de Travaux Indépendants: Problèmes Juste-À-Temps et Travaux Interférants (in French). PhD thesis, Université François-Rabelais de Tours, Tours.
Zurück zum Zitat Tuong, N. H., Soukhal, A., & Billaut, J.-C. (2012). Single-machine multi-agent scheduling problems with a global objective function. Journal of Scheduling, 15, 311–321. Tuong, N. H., Soukhal, A., & Billaut, J.-C. (2012). Single-machine multi-agent scheduling problems with a global objective function. Journal of Scheduling, 15, 311–321.
Zurück zum Zitat Tuzikov, A., Makhaniok, M., & Manner, R. (1998). Bicriterion scheduling of identical processing time jobs by uniform processors. Computers and Operations Research, 25, 31–35. Tuzikov, A., Makhaniok, M., & Manner, R. (1998). Bicriterion scheduling of identical processing time jobs by uniform processors. Computers and Operations Research, 25, 31–35.
Zurück zum Zitat Uzsoy, R., & Yang, Y. (1997). Minimizing total weighted completion time on a single batch processing machine. Production and Operations Management, 6, 57–73. Uzsoy, R., & Yang, Y. (1997). Minimizing total weighted completion time on a single batch processing machine. Production and Operations Management, 6, 57–73.
Zurück zum Zitat Van de Velde, S. (1991). Machine scheduling and Lagrangian relaxation. PhD thesis, CWI Amsterdam. Van de Velde, S. (1991). Machine scheduling and Lagrangian relaxation. PhD thesis, CWI Amsterdam.
Zurück zum Zitat Van Wassenhove, L. N., & Gelders, L. F. (1980). Solving a bicriterion problem. European Journal of Operational Research, 4(1), 42–48. Van Wassenhove, L. N., & Gelders, L. F. (1980). Solving a bicriterion problem. European Journal of Operational Research, 4(1), 42–48.
Zurück zum Zitat Vazirani, V. V. (2003). Approximation algorithms (2nd ed.). Berlin/Heidelberg: Springer. Vazirani, V. V. (2003). Approximation algorithms (2nd ed.). Berlin/Heidelberg: Springer.
Zurück zum Zitat Vickson, R. G. (1980a). Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine. Operations Research, 28, 1155–1167. Vickson, R. G. (1980a). Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine. Operations Research, 28, 1155–1167.
Zurück zum Zitat Vickson, R. G. (1980b). Two single machine sequencing problems involving controllable job processing times. AIIE Transactions, 12, 258–262. Vickson, R. G. (1980b). Two single machine sequencing problems involving controllable job processing times. AIIE Transactions, 12, 258–262.
Zurück zum Zitat Wagner, H. M. (1959). An integer linear programming model for machine scheduling. Naval Research Logistic Quarterly, 6, 131–140. Wagner, H. M. (1959). An integer linear programming model for machine scheduling. Naval Research Logistic Quarterly, 6, 131–140.
Zurück zum Zitat Walukiewicz, S. (1991). Integer programming. Warszawa: Polish Scientific Publishers. Walukiewicz, S. (1991). Integer programming. Warszawa: Polish Scientific Publishers.
Zurück zum Zitat Wan, G., Yen, B. P. C., & Li, C. L. (2001). Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard. Information Processing Letters, 79, 273–280. Wan, G., Yen, B. P. C., & Li, C. L. (2001). Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard. Information Processing Letters, 79, 273–280.
Zurück zum Zitat Wan, G., Leung, J.-Y., & Pinedo, M. (2010). Scheduling two agents with controllable processing times. European Journal of Operational Research, 205, 528–539. Wan, G., Leung, J.-Y., & Pinedo, M. (2010). Scheduling two agents with controllable processing times. European Journal of Operational Research, 205, 528–539.
Zurück zum Zitat Wan, L., Yuan, J., & Geng, Z. (2013, to appear). A note on the preemptive scheduling to minimize total completion time with release and deadline constraints. Journal of Scheduling. Wan, L., Yuan, J., & Geng, Z. (2013, to appear). A note on the preemptive scheduling to minimize total completion time with release and deadline constraints. Journal of Scheduling.
Zurück zum Zitat Webster, S., & Baker, K. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43, 692–704. Webster, S., & Baker, K. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43, 692–704.
Zurück zum Zitat Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey. Lecture Notes in Computer Science, 2570, 187–205. Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey. Lecture Notes in Computer Science, 2570, 187–205.
Zurück zum Zitat Wu, W. H. (2013). An exact and meta-heuristic approach for two-agent single-machine scheduling problem. Journal of Marine Science and Technology, 21, 215–221. Wu, W. H. (2013). An exact and meta-heuristic approach for two-agent single-machine scheduling problem. Journal of Marine Science and Technology, 21, 215–221.
Zurück zum Zitat Wu, C. C., Huang, S. K., & Lee, W. C. (2011). Two-agent scheduling with learning consideration. Computers and Industrial Engineering, 61, 1324–1335. Wu, C. C., Huang, S. K., & Lee, W. C. (2011). Two-agent scheduling with learning consideration. Computers and Industrial Engineering, 61, 1324–1335.
Zurück zum Zitat Wu, W. H., Cheng, S. R., Wu, C. C., & Yin, Y. Q. (2012). Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations. Journal of Intelligent Manufacturing, 23, 1985–1993. Wu, W. H., Cheng, S. R., Wu, C. C., & Yin, Y. Q. (2012). Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations. Journal of Intelligent Manufacturing, 23, 1985–1993.
Zurück zum Zitat Wu, C.-C., Wu, W.-H., Chen, J.-C., Yin, Y., & Wu, W.-H. (2013a). A study of the single-machine two-agent scheduling problem with release times. Applied Soft Computing, 13, 998–1006. Wu, C.-C., Wu, W.-H., Chen, J.-C., Yin, Y., & Wu, W.-H. (2013a). A study of the single-machine two-agent scheduling problem with release times. Applied Soft Computing, 13, 998–1006.
Zurück zum Zitat Wu, W. H., Xu, J., Wu, W., Yin, Y., Cheng, I., & Wu, C. C. (2013b). A tabu method for a two-agent single-machine scheduling with deterioration jobs. Computers & Operations Research, 40, 2116–2127. Wu, W. H., Xu, J., Wu, W., Yin, Y., Cheng, I., & Wu, C. C. (2013b). A tabu method for a two-agent single-machine scheduling with deterioration jobs. Computers & Operations Research, 40, 2116–2127.
Zurück zum Zitat Yin, Y. Q., Cheng, S. R., Cheng, T., Wu, C. C., & Wu, W.-H. (2012a). Two-agent single-machine scheduling with assignable due dates. Applied Mathematics and Computation, 219, 1674–1685. Yin, Y. Q., Cheng, S. R., Cheng, T., Wu, C. C., & Wu, W.-H. (2012a). Two-agent single-machine scheduling with assignable due dates. Applied Mathematics and Computation, 219, 1674–1685.
Zurück zum Zitat Yin, Y. Q., Cheng, S. R., & Wu, C. C. (2012b). Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Information Sciences, 189, 282–292. Yin, Y. Q., Cheng, S. R., & Wu, C. C. (2012b). Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Information Sciences, 189, 282–292.
Zurück zum Zitat Yin, Y. Q., Wu, W., Cheng, S. R., & Wu, C. C. (2012c). An investigation on a two-agent single-machine scheduling problem with unequal release dates. Computers & Operations Research, 39, 3062–3073. Yin, Y. Q., Wu, W., Cheng, S. R., & Wu, C. C. (2012c). An investigation on a two-agent single-machine scheduling problem with unequal release dates. Computers & Operations Research, 39, 3062–3073.
Zurück zum Zitat Yuan, J. J., Shang, W. P., & Feng, Q. (2005). A note on the scheduling with two families of jobs. Journal of Scheduling, 8, 537–542. Yuan, J. J., Shang, W. P., & Feng, Q. (2005). A note on the scheduling with two families of jobs. Journal of Scheduling, 8, 537–542.
Zurück zum Zitat Zhao, K., & Lu, X. (2013). Approximation schemes for two-agent scheduling on parallel machines. Theoretical Computer Science, 468, 114–121. Zhao, K., & Lu, X. (2013). Approximation schemes for two-agent scheduling on parallel machines. Theoretical Computer Science, 468, 114–121.
Zurück zum Zitat Zitzler, E., Knowles, J., & Thiele, L. (2008). Quality assessment of Pareto set approximations. Lecture Notes in Computer Science, 5252 LNCS, 373–404. Zitzler, E., Knowles, J., & Thiele, L. (2008). Quality assessment of Pareto set approximations. Lecture Notes in Computer Science, 5252 LNCS, 373–404.
Metadaten
Titel
Batching Scheduling Problems
verfasst von
Alessandro Agnetis
Jean-Charles Billaut
Stanisław Gawiejnowicz
Dario Pacciarelli
Ameur Soukhal
Copyright-Jahr
2014
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-41880-8_4