IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v47y1999i5p744-756.html
   My bibliography  Save this article

Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow

Author

Listed:
  • S. Thomas McCormick

    (Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, British Columbia V6T 1Z2, Canada)

Abstract

Chen (1994) develops an attractive variant of the classical problem of preemptively scheduling independent jobs with release dates and due dates. Chen suggests that in practice one can often pay to reduce the processing requirement of a job. This leads to two parametric max flow problems. Serafini (1996) considers scheduling independent jobs with due dates on multiple machines, where jobs can be split among machines so that pieces of a single job can execute in parallel. Minimizing the maximum tardiness again gives a parametric max flow problem. A third problem of this type is deciding how many more games a baseball team can lose part way through a season without being eliminated from finishing first (assuming a best possible distribution of wins and losses by other teams). A fourth such problem is an extended selection problem of Brumelle et al. (1995a), where we want to discount the costs of “tree-structured” tools as little as possible to be able to process all jobs at a profit.It is tempting to try to solve these problems with the parametric push-relabel max flow methods of Gallo et al. (GGT) (1989). However, all these applications appear to violate the conditions necessary to apply GGT. We extend GGT in three ways that allow it to be applied to all four of the above applications. We also consider some other applications where these ideas apply. Our extensions to GGT yield faster algorithms for all these applications.

Suggested Citation

  • S. Thomas McCormick, 1999. "Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow," Operations Research, INFORMS, vol. 47(5), pages 744-756, October.
  • Handle: RePEc:inm:oropre:v:47:y:1999:i:5:p:744-756
    DOI: 10.1287/opre.47.5.744
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.47.5.744
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.47.5.744?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Chen, Y. L., 1994. "Scheduling jobs to minimize total cost," European Journal of Operational Research, Elsevier, vol. 74(1), pages 111-119, April.
    2. Paolo Serafini, 1996. "Scheduling Jobs on Several Machines with the Job Splitting Property," Operations Research, INFORMS, vol. 44(4), pages 617-628, August.
    3. A. Federgruen & H. Groenevelt, 1986. "Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques," Management Science, INFORMS, vol. 32(3), pages 341-349, March.
    4. Werner Dinkelbach, 1967. "On Nonlinear Fractional Programming," Management Science, INFORMS, vol. 13(7), pages 492-498, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Russell, Tyrel & van Beek, Peter, 2012. "A hybrid constraint programming and enumeration approach for solving NHL playoff qualification and elimination problems," European Journal of Operational Research, Elsevier, vol. 218(3), pages 819-828.
    2. Maria Scutellà, 2007. "A note on the parametric maximum flow problem and some related reoptimization issues," Annals of Operations Research, Springer, vol. 150(1), pages 231-244, March.
    3. Sedeño-Noda, A. & de Pablo, D. Alcaide López & González-Martín, C., 2009. "A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows," European Journal of Operational Research, Elsevier, vol. 196(1), pages 140-154, July.
    4. Ilan Adler & Alan L. Erera & Dorit S. Hochbaum & Eli V. Olinick, 2002. "Baseball, Optimization, and the World Wide Web," Interfaces, INFORMS, vol. 32(2), pages 12-22, April.
    5. Nir Halman & Mikhail Y. Kovalyov & Alain Quilliot, 2023. "Max–max, max–min, min–max and min–min knapsack problems with a parametric constraint," 4OR, Springer, vol. 21(2), pages 235-246, June.
    6. Akiyoshi Shioura & Natalia V. Shakhlevich & Vitaly A. Strusevich, 2016. "Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 148-161, February.
    7. Shioura, Akiyoshi & Shakhlevich, Natalia V. & Strusevich, Vitaly A., 2018. "Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches," European Journal of Operational Research, Elsevier, vol. 266(3), pages 795-818.
    8. Akiyoshi Shioura & Natalia V. Shakhlevich & Vitaly A. Strusevich, 2020. "Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost," Journal of Global Optimization, Springer, vol. 76(3), pages 471-490, March.
    9. Stephan Helfrich & Arne Herzel & Stefan Ruzika & Clemens Thielen, 2022. "An approximation algorithm for a general class of multi-parametric optimization problems," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 1459-1494, October.
    10. Sedeno-Noda, A. & Alcaide, D. & Gonzalez-Martin, C., 2006. "Network flow approaches to pre-emptive open-shop scheduling problems with time-windows," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1501-1518, November.
    11. Cristina Bazgan & Arne Herzel & Stefan Ruzika & Clemens Thielen & Daniel Vanderpooten, 2022. "An approximation algorithm for a general class of parametric optimization problems," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1328-1358, July.
    12. Akiyoshi Shioura & Natalia V. Shakhlevich & Vitaly A. Strusevich, 2017. "Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 724-736, November.
    13. Klamroth, Kathrin & Wiecek, Margaret M., 2001. "A time-dependent multiple criteria single-machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 135(1), pages 17-26, November.
    14. Akiyoshi Shioura & Vitaly A. Strusevich & Natalia V. Shakhlevich, 2024. "Preemptive scheduling of parallel jobs of two sizes with controllable processing times," Journal of Scheduling, Springer, vol. 27(2), pages 203-224, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sedeno-Noda, A. & Alcaide, D. & Gonzalez-Martin, C., 2006. "Network flow approaches to pre-emptive open-shop scheduling problems with time-windows," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1501-1518, November.
    2. Sedeño-Noda, A. & de Pablo, D. Alcaide López & González-Martín, C., 2009. "A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows," European Journal of Operational Research, Elsevier, vol. 196(1), pages 140-154, July.
    3. Shioura, Akiyoshi & Shakhlevich, Natalia V. & Strusevich, Vitaly A., 2018. "Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches," European Journal of Operational Research, Elsevier, vol. 266(3), pages 795-818.
    4. Tunjo Perić & Josip Matejaš & Zoran Babić, 2023. "Advantages, sensitivity and application efficiency of the new iterative method to solve multi-objective linear fractional programming problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(3), pages 751-767, September.
    5. Luca Consolini & Marco Locatelli & Jiulin Wang & Yong Xia, 2020. "Efficient local search procedures for quadratic fractional programming problems," Computational Optimization and Applications, Springer, vol. 76(1), pages 201-232, May.
    6. Harald Dyckhoff & Katrin Allen, 1999. "Theoretische Begründung einer Effizienzanalyse mittels Data Envelopment Analysis (DEA)," Schmalenbach Journal of Business Research, Springer, vol. 51(5), pages 411-436, May.
    7. Feng Guo & Liguo Jiao, 2023. "A new scheme for approximating the weakly efficient solution set of vector rational optimization problems," Journal of Global Optimization, Springer, vol. 86(4), pages 905-930, August.
    8. Maziar Sahamkhadam, 2021. "Dynamic copula-based expectile portfolios," Journal of Asset Management, Palgrave Macmillan, vol. 22(3), pages 209-223, May.
    9. Cook, Wade D. & Zhu, Joe, 2007. "Within-group common weights in DEA: An analysis of power plant efficiency," European Journal of Operational Research, Elsevier, vol. 178(1), pages 207-216, April.
    10. Laurent Alfandari & Alborz Hassanzadeh & Ivana Ljubić, 2021. "An Exact Method for Assortment Optimization under the Nested Logit Model," Working Papers hal-02463159, HAL.
    11. A. Roubi, 2000. "Method of Centers for Generalized Fractional Programming," Journal of Optimization Theory and Applications, Springer, vol. 107(1), pages 123-143, October.
    12. Jun-Ho Lee & Hyun-Jung Kim, 2021. "A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence-dependent setup times, and limited setup operators," Flexible Services and Manufacturing Journal, Springer, vol. 33(4), pages 992-1026, December.
    13. Andrés Gómez & Oleg A. Prokopyev, 2021. "A Mixed-Integer Fractional Optimization Approach to Best Subset Selection," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 551-565, May.
    14. Keshav Singh & Meng-Lin Ku & Sudip Biswas & Tharmalingam Ratnarajah, 2017. "Energy-Efficient Subcarrier Pairing and Power Allocation for DF Relay Networks with an Eavesdropper," Energies, MDPI, vol. 10(12), pages 1-13, November.
    15. Mehdi Nooshyar & Abdolrasoul Sakhaei Gharagezlou & Nima Imani & Elhameh Mikaeili & Mahdi Nangir, 2024. "Energy efficiency analysis for 5G application in massive MIMO systems by using lower bound inequality and SCAM method," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 85(3), pages 365-372, March.
    16. Claassen, G.D.H., 2014. "Mixed integer (0–1) fractional programming for decision support in paper production industry," Omega, Elsevier, vol. 43(C), pages 21-29.
    17. Bo Zhang & YueLin Gao & Xia Liu & XiaoLi Huang, 2022. "An Outcome-Space-Based Branch-and-Bound Algorithm for a Class of Sum-of-Fractions Problems," Journal of Optimization Theory and Applications, Springer, vol. 192(3), pages 830-855, March.
    18. Hasuike, Takashi & Ishii, Hiroaki, 2009. "On flexible product-mix decision problems under randomness and fuzziness," Omega, Elsevier, vol. 37(4), pages 770-787, August.
    19. Welington Oliveira & Valentina Sessa & David Sossa, 2024. "Computing Critical Angles Between Two Convex Cones," Journal of Optimization Theory and Applications, Springer, vol. 201(2), pages 866-898, May.
    20. R. Yamamoto & H. Konno, 2007. "An Efficient Algorithm for Solving Convex–Convex Quadratic Fractional Programs," Journal of Optimization Theory and Applications, Springer, vol. 133(2), pages 241-255, May.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:47:y:1999:i:5:p:744-756. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.