Solving the selective multi-category parallel-servicing problem

详细信息    查看全文

• 作者：Troels Martin Range (1)
  Richard Martin Lusby (2)
  Jesper Larsen (2)
  
  1. Department of Business and Economics ; COHERE ; University of Southern Denmark ; Campusvej 55 ; 5230聽 ; Odense M ; Denmark
  2. Department of Engineering Management ; Technical University of Denmark ; Produktionstorvet ; building 426 ; 2800聽 ; Kgs. Lyngby ; Denmark
  
• 关键词：Machine scheduling ; Dynamic programming ; Node ; disjoint shortest path problem ; preprocessing ; 90B35 ; 90C35
• 刊名：Journal of Scheduling
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：18
• 期：2
• 页码：165-184
• 全文大小：396 KB
• 参考文献：1. Ahuja, RK, Magnanti, TL, Orlin, JB (1993) Network flows鈥擳heory, algorithms, and applications. Prentice Hall, Upper Saddle River, NJ
  2. Anbil, R, Barnhart, C, Hatay, L, Johnson, EL, Ramakrishnan, VS Crew-pairing optimization at american airlines decision technilogies. In: Ciriani, TA, Leachman, RC eds. (1993) Optimization in industry. Wiley, New York, pp. 31-36
  3. Andersson, E., Housos, E., Kohl, N., & Wedelin, D. (1998). Crew pairing optimization. In / OR in airline industry. Dordrecht: Kluwer.
  4. Ar谩oz, J, Fern谩ndez, E, Zoltan, C (2006) Privatized rural postman problems. Computers & Operations Research 33: pp. 3432-3449 CrossRef
  5. Bang-Jensen, J., & Gutin, G. (2001). / Digraphs: Theory, algorithms and applications. Springer monographs in mathematics. New York: Springer.
  6. Black, D, Eglese, R, W酶hlk, S (2013) The time-dependent prize-collecting arc routing problem. Computers and Operations Research 40: pp. 526-535 CrossRef
  7. Chen, Z-L, Powell, WB (1999) Solving parallel machine scheduling problems by column generation. INFORMS Journal on Computing 11: pp. 78 CrossRef
  8. Cormen, TH, Leiserson, CE, Rivest, RL, Stein, C (2001) Introduction to algorithms. MIT Press, Cambridge
  9. Demeester, P, Souffriau, W, Causmaecker, PD, Berghe, GV (2010) A hybrid tabu search algorithm for automatically assigning patients to beds. Artificial Intelligence in Medicine 48: pp. 61-70 CrossRef
  10. Desrochers, M, Desrosiers, J, Solomon, M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Operations Research 40: pp. 342 CrossRef
  11. Drexl, M (2012) Rich vehicle routing in theory and practice. Logistics Research 5: pp. 47-63 CrossRef
  12. Feillet, D, Dejax, P, Gendreau, M (2005) Travelling salesman problem with profits. Transportation Science 39: pp. 188-205 CrossRef
  13. Garey, MR (1976) The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research 1: pp. 117-129 CrossRef
  14. Gilmore, P, Gomory, R (1961) A linear programming approach to the cutting-stock problem. Operations Research 9: pp. 849-859 CrossRef
  15. Haouri, M, Layeb, SB, Sherali, H (2013) Tight compact models and comparative analysis for the prize collecting Steiner tree problem. Discrete Applied Mathematics 161: pp. 618-632 CrossRef
  16. Irnich, S (2008) Resource extension functions: Properties, inversion, and generalization to segments. OR Spectrum 30: pp. 113-148 CrossRef
  17. Irnich, S., & Desaulniers, G. (2005). / Shortest path problems with resource constraints (Chap. 2). New York: Springer.
  18. Pisinger, D. (1995). Algorithms for Knapsack problems. PhD thesis, Department of Computer Science, Copenhagen University.
  19. Range, T. M., Lusby, R. M., & Larsen, J. (2013). A column generation approach for solving the patient admission scheduling problem. Discussion Papers on Business and Economics 1/2013, Department of Business and Economics, University of Southern Denmark.
  20. Smith-Miles, K., & Lopes, L. (2012). Measuring instance difficulty for combinatorial optimization problems. / Computers and Operations Research, / 39, 875鈥?89.
  21. Suurballe, J. W., & Tarjan, R. E. (1984). A quick method for finding shortest pairs of disjoint paths. / Networks, / 14, 325鈥?36.
  22. Tholey, T. (2005). / Finding disjoint paths on directed acyclic graphs. Lecture notes in computer science (Vol. 3787, pp. 319鈥?30). Berlin: Springer.
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Calculus of Variations and Optimal Control
  Optimization
  Artificial Intelligence and Robotics
  Production and Logistics
  
• 出版者：Springer Netherlands
• ISSN：1099-1425

文摘

In this paper, we present a new scheduling problem and describe a shortest path-based heuristic as well as a dynamic programming-based exact optimization algorithm to solve it. The selective multi-category parallel-servicing problem arises when a set of jobs has to be scheduled on a server (machine) with limited capacity. Each job requests service in a prespecified time window and belongs to a certain category. Jobs may be serviced partially, incurring a penalty; however, only jobs of the same category can be processed simultaneously. One must identify the best subset of jobs to process in each time interval of a given planning horizon, while respecting the server capacity and scheduling requirements. We compare the proposed solution methods with a Mixed Integer Linear Programming (MILP) formulation and show that the dynamic programming approach is faster when the number of categories is large, whereas the MILP can be solved faster when the number of categories is small.