Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Multiagent Scheduling Fundamentals Read chapter Read first chapter

2014 | OriginalPaper | Chapter

4. Batching Scheduling Problems

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

Published in: Multiagent Scheduling

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Single Machine Problems
next chapter Parallel Machine Scheduling Problems
Literature
Agnetis, A., Mirchandani, P., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52, 229–242.
Agnetis, A., Pacciarelli, D., & Pacifici, A. (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150, 3–15.
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., 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., Nicosia, G., Pacifici, A., & Pferschy, U. (2013). Two agents competing for a shared machine. Lecture Notes in Computer Science, 8176 LNAI, 1–14.
Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The design and analysis of computer algorithms. Reading: Addison-Wesley.
Albers, S., & Brucker, P. (1993). The complexity of one-machine batching problems. Discrete Applied Mathematics, 47, 87–107.
Alidaee, B., & Womer, N. K. (1999). Scheduling with time dependent processing times: Review and extensions. Journal of the Operatational Research Society, 50, 711–720.
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.
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.
Arbib, C., Flammini, M., & Marinelli, F. (2003). Minimum flow time graph ordering. Lecture Notes on Computer Science, 2880, 23–33.
Bachman, A., & Janiak, A. (2000). Minimizing maximum lateness under linear deterioration. European Journal of Operational Research, 126, 557–566.
Bachman, A., & Janiak, A. (2004). Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society, 55, 257–264.
Baker, K., & Smith, J. C. (2003). A multiple criterion model for machine scheduling. Journal of Scheduling, 6, 7–16.
Balasubramanian, H., Fowler, J., Keha, A., & Pfund, M. (2009). Scheduling interfering job sets on parallel machines. European Journal of Operational Research, 199, 55–67.
Bellman, R. (1957). Dynamic programming. Princeton: Princeton University Press.
Bellman, R., & Dreyfus, S. E. (1962). Applied dynamic programming. Princeton: Princeton University Press.
Biskup, D. (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188, 315–329.
Blazewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling: From theory to applications. Berlin/Heidelberg: Springer.
Bowman, E. H. (1959). The schedule sequencing problem. Operations Research, 7, 621–624.
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.
Brucker, P. (2007). Scheduling algorithms (5th ed.). Berlin: Springer.
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., 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.
Bruno, J., Coffman, E. G., & Sethi, R. (1974). Scheduling indepedant tasks to reduce mean finishing time. Communications of the ACM, 17, 382–387.
Chen, Z.-L. (1996). Parallel machine scheduling with time dependent processing times. Discrete Applied Mathematics, 70, 81–93.
Chen, Z.-L. (1997). Erratum to parallel machine scheduling with time dependent processing times. Discrete Applied Mathematics, 75, 103.
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.
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., 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., 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., 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. (2008). Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research, 188, 603–609.
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., 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., 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.
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.
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.
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.
Conway, R., Maxwell, W., & Miller, L. (1967). Theory of scheduling. Reading: Addison-Wesley
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
Cormen, T. H., Leiserson, C. E., & Rivest, R. L. (1994). Introduction to algorithms. Cambridge: MIT.
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.
Dileepan, P., & Sen, T. (1988). Bicriterion static scheduling research for a single machine. Omega. The International Journal of Management Science, 16, 53–59.
Ding, G., & Sun, S. (2010). Single-machine scheduling problems with two agents competing for makespan. Lecture Notes in Computer Science, 6328, 244–255.
Du, J., & Leung, J. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of operations research, 15, 483–495.
Ehrgott, M., Shao, L., & Schobel, A. (2011). An approximation algorithm for convex multi-objective programming problems. Journal of Global Optimization, 50, 397–416.
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.
Fan, B., Cheng, T., Li, S., & Feng, Q. (2013). Bounded parallel-batching scheduling with two competing agents. Journal of Scheduling, 16, 261–271.
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.
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., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117–129.
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.
Gawiejnowicz, S. (1996). Brief survey of continuous models of scheduling. Foundations of Computing and Decision Sciences, 21, 81–100.
Gawiejnowicz, S. (2008). Time-dependent scheduling: EATCS monographs in theoretical computer science. Berlin/New York: Springer.
Gawiejnowicz, S., & Kononov, A. (2012, in press). Isomorphic scheduling problems. Annals of Operations Research. doi:10.1007/s10479-012-1222-2.
Gawiejnowicz, S., Onak, T., & Suwalski, C. (2006). A new library for evolutionary algorithms. Lecture Notes in Computer Science, 3911, 414–421.
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. (2009b). Equivalent time-dependent scheduling problems. European Journal of Operational Research, 196, 919–929.
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.
Geoffrion, A. M. (1968). Proper efficiency and the theory of vector maximization. Journal of Mathematical Analysis and Applications, 22, 618–630.
Geoffrion, A. M. (1974). Lagrangian relaxation for integer programming. Mathematical Programming Study, 2, 82–114.
Graham, R. L. (1966). Bounds for certain multiprocessor anomalies. Bell System Technical Journals, 17, 1563–1581.
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.
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.
Hochbaum, D. (1998). Approximation algorithms for NP-hard problems. Boston: PWS Publishing.
Hochbaum, D. S., & Landy, D. (1994). Scheduling with batching: Minimizing the weighted number of tardy jobs. Operations Research Letters, 16, 79–86.
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, H. (2005). Multicriteria scheduling. European Journal of Operational Research, 167, 592–623.
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.
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., & Ullman, J. (1979). Introduction to automata theory, languages and computation. Reading: Addison-Wesley.
Horn, W. A. (1973). Minimizing average flow time with parallel machines. Operations Research, 21, 846–847.
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. (2007b). Complexity of two dual criteria scheduling problems. Operations Research Letters, 35, 211–220.
Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness. In Management Science Research (Vol. 43). Los Angeles: University of California.
Johnson, S. M. (1954). Optimal two and three-stage production schedules with setup times included. Naval Research Logistic Quarterly, 1, 61–67.
Johnson, D. (1982). The NP-completeness column: An ongoing guide. Journal of Algorithms, 2, 393–405.
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.
Jozefowska, J. (2007). Just-in-time scheduling: Models and algorithms for computer and manufacturing systems. Berlin: Springer.
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.
Kellerer, H., & Strusevich, V. A. (2010). Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica, 57, 769–795.
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).
Knotts, G., Dror, M., & Hartman, B. C. (2000). Agent-based project scheduling. IIE Transactions, 32, 387–401.
Knuth, D. E. (1967–1969). The art of computer programming (Vols. 1–3). Reading: Addison-Wesley.
Kononov, A. (1997). Scheduling problems with linear increasing processing times. In Operations research September 3–6, 1996, Braunschweig (pp. 208–212). Springer.
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., & Gawiejnowicz, S. (2001). NP-hard cases in scheduling deteriorating jobs on dedicated machines. Journal of the Operational Research Society, 52, 708–718.
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. (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.
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.
Lawler, E. L. (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science, 19(8), 544–546.
Lawler, E. L. (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342.
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. (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., & Moore, J. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77–84.
Lee, C. (1991). Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics, 20, 53–61.
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, 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, 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., Chung, Y., & Hu, M. (2012). Genetic algorithms for a two-agent single-machine problem with release time. Applied Soft Computing, 12, 3580–3589.
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.
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., 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., Pinedo, M. L., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458–469.
Levin, A., & Woeginger, G. J. (2006). The constrained minimum weighted sum of job completion times problem. Mathematical Programming Series A, 108, 115–126.
Lew, A., & Mauch, H. (2007). Dynamic programming: A computational tool. Berlin/Heidelberg: Springer.
Lewis, H. R., & Papadimitriou, C. H. (1998). Elements of the theory of computation (2nd ed.). Upper Saddle River: Prentice-Hall.
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, S., & Yuan, J. (2012). Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 15, 629–640.
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. (2010a). Two-agent group scheduling with deteriorating jobs on a single machine. International Journal of Advanced Manufacturing Technology, 47, 657–664.
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., 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., & Gong, H. (2013). Scheduling two agents with sum-of-processing-times-based deterioration on a single machine. Applied Mathematics and Computation, 219, 8848–8855.
Manne, A. S. (1960). On the job-shop scheduling problem. Operations Research, 8, 219–223.
Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in multi-objective mathematical programming problems. Applied Mathematics and Computation, 213(2), 455–465.
Mc Naughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 6, 1–12.
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.
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.
Moore, J. M. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15, 102–109.
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. (2011). Single machine batch scheduling with two competing agents to minimize total flowtime. European Journal of Operational Research, 215(3), 524–531.
Mosheiov, G. (1994). Scheduling jobs under simple linear deterioration. Computers and Operations Research, 21, 653–659.
Mosheiov, G. (2002). Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete Applied Mathematics, 117, 195–209.
Nagar, A., Haddock, J., & Heragu, S. (1995). Multiple and bicriteria scheduling: A literature survey. European Journal of the Operational Research, 81, 88–104.
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.
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., Cheng, T., & Ng, C. (2011). Two-agent scheduling to minimize the total cost. European Journal of Operational Research, 215, 39–44.
Nowicki, E., & Zdrzalka, S. (1990). A survey of results for sequencing problems with controllable processing times. Discrete Applied Mathematics, 26, 271–287.
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., Finke, G., & Kuiten, A. K. (2009). Flowshop scheduling problem with batching machine and task compatibilities. Computers & Operations Research, 36, 391–401.
Papadimitriou, C. M. (1994). Computational complexity. Reading: Addison Wesley.
Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial optimization: Algorithms and complexity. Englewood Cliffs: Prentice-Hall.
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.
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.
Pinedo, M. (2008). Scheduling: Theory, algorithms, and systems (3rd ed.). Berlin: Springer.
Potts, C., & Kovalyov, M. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120(2), 228–249.
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.
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.
Queyranne, M. (1993). Structure of a simple scheduling polyhedron. Mathematical Programming, 58, 263–285.
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.
Ruzika, S., & Wiecek, M. M. (2005). Approximation methods in multiobjective programming. Journal of Optimization Theory and Applications, 126(3), 473–501.
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.
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.
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.
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.
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.
Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643–1666.
Smith, W. E. (1956). Various optimizer for single-stage production. Naval Research Logistics Quarterly, 3, 59–66.
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.
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).
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, V., & Billaut, J.-C. (2006). Multicriteria scheduling: Theory, models and algorithms (2nd ed.). Berlin/Heildelberg/New York: Springer.
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., Soukhal, A., & Billaut, J.-C. (2012). Single-machine multi-agent scheduling problems with a global objective function. Journal of Scheduling, 15, 311–321.
Tuzikov, A., Makhaniok, M., & Manner, R. (1998). Bicriterion scheduling of identical processing time jobs by uniform processors. Computers and Operations Research, 25, 31–35.
Uzsoy, R., & Yang, Y. (1997). Minimizing total weighted completion time on a single batch processing machine. Production and Operations Management, 6, 57–73.
Van de Velde, S. (1991). Machine scheduling and Lagrangian relaxation. PhD thesis, CWI Amsterdam.
Van Wassenhove, L. N., & Gelders, L. F. (1980). Solving a bicriterion problem. European Journal of Operational Research, 4(1), 42–48.
Vazirani, V. V. (2003). Approximation algorithms (2nd ed.). Berlin/Heidelberg: Springer.
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. (1980b). Two single machine sequencing problems involving controllable job processing times. AIIE Transactions, 12, 258–262.
Wagner, H. M. (1959). An integer linear programming model for machine scheduling. Naval Research Logistic Quarterly, 6, 131–140.
Walukiewicz, S. (1991). Integer programming. Warszawa: Polish Scientific Publishers.
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., Leung, J.-Y., & Pinedo, M. (2010). Scheduling two agents with controllable processing times. European Journal of Operational Research, 205, 528–539.
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.
Webster, S., & Baker, K. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43, 692–704.
Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey. Lecture Notes in Computer Science, 2570, 187–205.
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, C. C., Huang, S. K., & Lee, W. C. (2011). Two-agent scheduling with learning consideration. Computers and Industrial Engineering, 61, 1324–1335.
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, 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, 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.
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., & 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., 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.
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.
Zhao, K., & Lu, X. (2013). Approximation schemes for two-agent scheduling on parallel machines. Theoretical Computer Science, 468, 114–121.
Zitzler, E., Knowles, J., & Thiele, L. (2008). Quality assessment of Pareto set approximations. Lecture Notes in Computer Science, 5252 LNCS, 373–404.
Metadata
Title
Batching Scheduling Problems
Authors
Alessandro Agnetis
Jean-Charles Billaut
Stanisław Gawiejnowicz
Dario Pacciarelli
Ameur Soukhal
Copyright Year
2014
Publisher
Springer Berlin Heidelberg
Book
Multiagent Scheduling

Print ISBN: 978-3-642-41879-2

Electronic ISBN: 978-3-642-41880-8

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-642-41880-8_4