연구동향 분석

Integer Optimization Models and Algorithms for the Multi-Period Non-Shareable Resource Allocation Problem = 다기간 비공유 자원 할당 문제에 대한 정수최적화 모형 및 해법

박종윤 2022년

논문상세정보
인용/피인용
' Integer Optimization Models and Algorithms for the Multi-Period Non-Shareable Resource Allocation Problem = 다기간 비공유 자원 할당 문제에 대한 정수최적화 모형 및 해법' 의 주제별 논문영향력
논문영향력 선정 방법
논문영향력 요약
주제
  • 제조공업
  • Branch-and-price
  • Column generation
  • Integer optimization
  • LP-based heuristic
  • Multi-period non-shareable resource allocation problem
  • Resource constrained scheduling problem
동일주제 총논문수 논문피인용 총횟수 주제별 논문영향력의 평균
124 0

0.0%

' Integer Optimization Models and Algorithms for the Multi-Period Non-Shareable Resource Allocation Problem = 다기간 비공유 자원 할당 문제에 대한 정수최적화 모형 및 해법' 의 참고문헌

  • [9] A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, and B. Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM (JACM), 48 (2001), pp. 1069–1090.
    [2001]
  • [8] , A logarithmic approximation for unsplittable flow on line graphs, ACM Transactions on Algorithms (TALG), 10 (2014), pp. 1–15.
    [2014]
  • [81] L. A. Wolsey, Integer programming, Wiley, 2 ed., 2020.
    [2020]
  • [80] J. We¸glarz, J. J´ozefowska, M. Mika, and G. Walig´ora, Project scheduling with finite or infinite number of activity processing modes - a survey, European Journal of Operational Research, 208 (2011), pp. 177–205.
    [2011]
  • [7] N. Bansal, Z. Friggstad, R. Khandekar, and M. R. Salavatipour, A logarithmic approximation for unsplittable flow on line graphs, in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’09, USA, 2009, Society for Industrial and Applied Mathematics, pp. 702–709.
    [2009]
  • [78] F. Vanderbeck and L. A. Wolsey, Reformulation and decomposition of integer programs, in 50 Years of Integer Programming 1958-2008, M. J¨unger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, eds., Springer, 2010, pp. 431–502.
    [2010]
  • [77] P. H. Vance, C. Barnhart, E. L. Johnson, and G. L. Nemhauser, Airline crew scheduling: A new formulation and decomposition algorithm, Operations Research, 45 (1997), pp. 188–200.
    [1997]
  • [76] J. M. van den Akker, J. A. Hoogeveen, and S. L. van de Velde, Parallel machine scheduling by column generation, Operations Research, 47 (1999), pp. 862–872.
    [1999]
  • [74] M. Shariatmadari, N. Nahavandi, S. H. Zegordi, and M. H. Sobhiyah, Integrated resource management for simultaneous project selection and scheduling, Computers & Industrial Engineering, 109 (2017), pp. 39–47.
    [2017]
  • [73] C. Schwindt and J. Zimmermann, eds., Handbook on Project Management and Scheduling Vol.1, Springer, 2015.
    [2015]
  • [72] A. A. B. Pritsker, L. J. Waiters, and P. M. Wolfe, Multiproject scheduling with limited resources: a zero-one programming approach, Management Science, 16 (1969), pp. 93–108.
    [1969]
  • [71] C. A. Phillips, R. N. Uma, and J. Wein, Off-line admission control for general scheduling problems, Journal of Scheduling, 3 (2000), pp. 365–381.
    [2000]
  • [70] A. Parmentier and F. Meunier, Aircraft routing and crew pairing: updated algorithms at air france, Omega, 93 (2020), p. 102073.
    [2020]
  • [6] N. Bansal, A. Chakrabarti, A. Epstein, and B. Schieber, A quasi-ptas for unsplittable flow on line graphs, in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC ’06, New York, NY, USA, 2006, Association for Computing Machinery, p. 721–729.
    [2006]
  • [69] J. Park, J. Han, and K. Lee, Integer optimization model and algorithm for the stem cell culturing problem, Omega, 108 (2022), p. 102566.
  • [68] R. H. M¨ohring and M. Uetz, Scheduling scarce resources in chemical engineering, in Mathematics - Key Technology for the Future, W. J¨ager and H.-J. Krebs, eds., Springer, 2003, pp. 637–650.
    [2003]
  • [67] M. Mika, G. Walig´ora, and J. We¸glarz, Overview and state of the art, in Handbook on Project Management and Scheduling Vol.1, C. Schwindt and J. Zimmermann, eds., Springer, 2015, pp. 445–490.
    [2015]
  • [66] F. Margot, Symmetry in integer linear programming, in 50 Years of Integer Programming 1958-2008, M. J¨unger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, eds., Springer, 2010, pp. 647–686.
    [2010]
  • [65] V. Maniezzo and A. Mingozzi, The project scheduling problem with irregular starting time costs, Operations Research Letters, 25 (1999), pp. 175–182.
    [1999]
  • [62] R. Kolisch and R. Padman, An integrated survey of deterministic project scheduling, Omega, 29 (2001), pp. 249–272.
    [2001]
  • [61] R. Kolisch and K. Meyer, Selection and scheduling of pharmaceutical research projects, in Perspectives in Modern Project Scheduling, J. J´ozefowska and J. Weglarz, eds., Springer, 2006, pp. 321–344.
    [2006]
  • [60] H. Kellerer, U. Pferschy, and D. Pisinger, Multidimensional knapsack problems, in Knapsack Problems, Springer, 2004, pp. 235–283.
    [2004]
  • [57] W. Herroelen, B. De Reyck, and E. Demeulemeester, Resourceconstrained project scheduling: A survey of recent developments, Computers & Operations Research, 25 (1998), pp. 279–302.
    [1998]
  • [56] W. Herroelen, Project scheduling—theory and practice, Production and Operations Management, 14 (2005), pp. 413–432.
    [2005]
  • [54] , An updated survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 297 (2022), pp. 1–14.
  • [52] , Time-varying resource requirements and capacities, in Handbook on Project Management and Scheduling Vol.1, C. Schwindt and J. Zimmermann, eds., Springer, 2015, pp. 163–176.
    [2015]
  • [51] , Project scheduling with resource capacities and requests varying with time: a case study, Flexible Services and Manufacturing Journal, 25 (2013), pp. 74–93.
    [2013]
  • [49] T. Gschwind and S. Irnich, Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities, OR spectrum, 39 (2017), pp. 541–556.
    [2017]
  • [48] , A (5/3+ ε)-approximation for unsplittable flow on a path: placing small tasks into boxes, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, New York, NY, USA, 2018, Association for Computing Machinery, p. 607–619.
  • [47] F. Grandoni, T. M¨omke, A. Wiese, and H. Zhou, To augment or not to augment: solving unsplittable flow on a path by creating slack, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, USA, 2017, Society for Industrial and Applied Mathematics, pp. 2411–2422.
    [2017]
  • [46] , A linear programming approach to the cutting stock problem-part ii, Operations Research, 11 (1963), pp. 863–888.
    [1963]
  • [45] P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting-stock problem, Operations Research, 9 (1961), pp. 849–859.
    [1961]
  • [44] M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman and Company, 1979.
    [1979]
  • [42] FICO, Xpress-optimizer 8.9. http://www.fico.com/en. Accessed: 2020-05-27.
  • [40] M. Desrochers, J. Desrosiers, and M. M. Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, 40 (1992), pp. 342–354.
    [1992]
  • [3] C. Arbib and F. Marinelli, On cutting stock with due dates, Omega, 46 (2014), pp. 11–20.
    [2014]
  • [39] G. Desaulniers, J. Desrosiers, and M. M. Solomon, Column generation, vol. 5, Springer, 2005.
    [2005]
  • [38] A. Darmann, U. Pferschy, and J. Schauer, Resource allocation with time intervals, Theoretical Computer Science, 411 (2010), pp. 4217–4234.
    [2010]
  • [37] M. Conforti, G. Cornu´ejols, and G. Zambelli, Integer programming, Springer, 2014.
    [2014]
  • [36] F. Clautiaux, B. Detienne, and G. Guillot, An iterative dynamic programming approach for the temporal knapsack problem, European Journal of Operational Research, 293 (2021), pp. 442–456.
  • [35] M. Chrobak, G. J. Woeginger, K. Makino, and H. Xu, Caching is hard—even in the fault model, Algorithmica, 63 (2012), p. 781–794.
    [2012]
  • [34] M. Chrobak, H. Karloof, T. Payne, and S. Vishwnathan, New ressults on server problems, SIAM Journal on Discrete Mathematics, 4 (1991), p. 172–181.
    [1991]
  • [32] B. Chen, R. Hassin, and M. Tzur, Allocation of bandwidth and storage, IIE Transactions, 34 (2002), pp. 501–507.
    [2002]
  • [31] , Multicommodity demand flow in a tree and packing integer programs, ACM Transactions on Algorithms (TALG), 3 (2007), pp. 27–es.
    [2007]
  • [30] C. Chekuri, M. Mydlarz, and F. B. Shepherd, Multicommodity demand flow in a tree, in Automata, Languages and Programming, ICALP 2003, Berlin, Heidelberg, 2003, Springer Berlin Heidelberg, pp. 410–425.
    [2003]
  • [2] A. Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese, A mazing 2+ε approximation for unsplittable flow on a path, ACM Transactions on Algorithms (TALG), 14 (2018), pp. 1–23.
    [2018]
  • [29] A. Chakrabarti, C. Chekuri, A. Gupta, and A. Kumar, Approximation algorithms for the unsplittable flow problem, Algorithmica, 47 (2007), pp. 53–78.
    [2007]
  • [28] A. Chakrabarti, C. Chekuri, A. Gupta, and A. Kumar, Approximation algorithms for the unsplittable flow problem, in Approximation Algorithms for Combinatorial Optimization, APPROX 2002, Berlin, Heidelberg, 2002, Springer Berlin Heidelberg, pp. 51–66.
    [2002]
  • [27] C. C. B. Cavalcante, C. C. de Souza, M. W. P. Savelsbergh, Y.Wang, and L. A. Wolsey, Scheduling projects with labor constraints, Discrete Applied Mathematics, 112 (2001), pp. 27–52.
    [2001]
  • [26] A. Caprara, F. Furini, E. Malaguti, and E. Traversi, Solving the temporal knapsack problem via recursive dantzig-wolfe reformulation, Information Processing Letters, 116 (2016), pp. 379–386.
    [2016]
  • [24] , An improved approximation algorithm for resource allocation, ACM Transactions on Algorithms (TALG), 7 (2011), pp. 1–7.
    [2011]
  • [23] G. Calinescu, A. Chakrabarti, H. Karloff, and Y. Rabani, Improved approximation algorithms for resource allocation, in Integer Programming and Combinatorial Optimization, IPCO 2002, Berlin, Heidelberg, 2002, Springer Berlin Heidelberg, pp. 401–414.
    [2002]
  • [21] P. Brucker, A. Drexl, R. H. M¨ohring, K. Neumann, and E. Pesch, Resource-constrained project scheduling: notation, classification, models, and methods, European Journal of Operational Research, 112 (1999), pp. 3–41.
    [1999]
  • [20] T. Breugem, B. T. van Rossum, T. Dollevoet, and D. Huisman, A column generation approach for the integrated crew re-planning problem, Omega, 107 (2022), p. 102555.
  • [1] S. Albers, S. Arora, and S. Khanna, Page replacement for general caching problems, in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’99, USA, 1999, Society for Industrial and Applied Mathematics, pp. 31–40.
    [1999]
  • [19] , A constant-factor approximation algorithm for unsplittable flow on paths, SIAM journal on computing, 43 (2014), p. 767–799.
    [2014]
  • [18] P. Bonsma, J. Schulz, and A. Wiese, A constant factor approximation algorithm for unsplittable flow on paths, in Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, USA, 2011, IEEE Computer Society, p. 47–56.
    [2011]
  • [17] J. Blazewicz, J. K. Lenstra, and A. H. G. R. Kan, Scheduling subject to resource constraints: classification and complexity, Discrete Applied Mathematics, 5 (1983), pp. 11–24.
    [1983]
  • [16] H. Ben Amor, J. Desrosiers, and J. M. Val´erio de Carvalho, Dualoptimal inequalities for stabilized column generation, Operations Research, 54 (2006), pp. 454–463.
    [2006]
  • [15] J. Batra, N. Garg, A. Kumar, T. M¨omke, and A. Wiese, New approximation schemes for unsplittable flow on a path, in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15, USA, 2015, Society for Industrial and Applied Mathematics, pp. 47–58.
    [2015]
  • [14] M. Bartusch, R. H. M¨ohring, and F. J. Radermacher, Scheduling project networks with resource constraints and time windows, Annals of Operations Research, 16 (1988), pp. 199–240.
    [1988]
  • [13] M. Bartlett, A. M. Frisch, Y. Hamadi, I. Miguel, S. A. Tarim, and C. Unsworth, The temporal knapsack problem and its solution, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2005, Berlin, Heidelberg, 2005, Springer Berlin Heidelberg, pp. 34–48.
    [2005]
  • [12] C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh, and P. H. Vance, Branch-and-price: column generation for solving huge integer programs, Operations Research, 46 (1998), pp. 316–329.
    [1998]
  • Uncommon dantzig-wolfe reformulation for the temporal knapsack problem
  • Topological sorting of large networks
    A . B. Kahn 5 ( [1962]
  • Successive sublimation methods for dynamic programming computation
    T. Ibaraki 11 ( [1987]
  • Scheduling projects with multi-skilled personnel by a hybrid milp/cp benders decomposition algorithm
  • Scheduling jobs with fixed start and end times
  • Resource-constrained project scheduling with time-resource tradeoffs : The nonpreemptive case
    F. B. Talbot 28 ( [1982]
  • Project selection , scheduling and resource allocation with time dependent returns
    J. Chen and R. G. Askin 193 (pp . 23 ? 34 [2009]
  • Project scheduling with multiple modes : a genetic algorithm
    S. Hartmann 102 ( [2001]
  • Project scheduling with multiple modes : A comparison of exact algorithms ,
  • Parallel-machine rescheduling with job unavailability and rejection
    D. Wang , Y. Yin , and T. Cheng 81 (pp . 246 ? 260 . [2018]
  • One for the price of two : a unified approach for approximating covering problems
    R. Bar-Yehuda 27 ( [2000]
  • Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier
  • Approximating the throughput of multiple machines in real-time scheduling
  • A survey of variants and extensions of the resource-constrained project scheduling problem
    S. Hartmann and D. Briskorn , 207 (pp . 1 ? 14 [2010]
  • A project scheduling problem with labour constraints and time-dependent activities requirements
  • A branch-and-price-and-cut algorithm for a pickup and delivery problem in retailing
  • A branch-and-price approach for trip sequence planning of high-speed train units
  • A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem
  • A 2-approximation algorithm for the undirected feedback vertex set problem ,