Johnson Phosavanh

About me

I am a final year PhD candidate at the Discipline of Business Analytics at the University of Sydney, supervised by Professor Daniel Oron and Dr Nam Ho-Nguyen. My research area is combinatorial optimization with a particular focus on scheduling theory and optimization with graphs.

Education

Doctor of Philosophy (Business)
The University of Sydney Jul 2022 — Dec 2025

  • Thesis title: Advances in Dynamic Scheduling Problems.

Bachelor of Advanced Studies (Honours)
The University of Sydney Feb 2021 — Dec 2021

  • First Class Honours with University Medal.
  • Honours in Business Analytics.

Bachelor of Science
The University of Sydney Feb 2018 — Dec 2020

  • Majors in Business Analytics and Data Science.

Research

Peer reviewed articles

  1. Phosavanh, J. & Matsypura, D. (2025). Centrality of shortest paths: algorithms and complexity results. INFORMS Journal on Computing. Advance online publication. https://doi.org/10.1287/ijoc.2024.0945

    The centrality of a node is often used to measure its importance to the structure of a network. Some centrality measures can be extended to measure the importance of a path. In this paper, we consider the problem of finding the most central shortest path. We show that the computational complexity of this problem depends on the measure of centrality used and, in the case of degree centrality, whether the network is weighted or not. We develop a polynomial algorithm for the most degree-central shortest path problem with the worst-case running time of \(O(|E||V|^2\Delta(G))\), where \(|V|\) is the number of vertices, \(|E|\) is the number of edges, and \(\Delta(G)\) is the maximum degree of the graph. In addition, we show that the same problem is NP-hard on a weighted graph. Furthermore, we show that the problem of finding the most betweenness-central shortest path is solvable in polynomial time, while finding the most closeness-central shortest path is NP-hard, regardless of whether the graph is weighted or not. We also develop an algorithm for finding the most betweenness-central shortest path with a running time of \(O(|E|^2|V|^2)\) on unweighted graphs and \(O(|E|^2|V|^2 + |V|^2\log(|V|))\) on graphs with positively weighted edges. To conclude our paper, we conduct a numerical study of our algorithms on synthetic and real-world networks and compare our results to the existing literature.

    @article{PhosavanhMatsypura2025,
title = {Centrality of shortest paths: algorithms and complexity results},
journal = {INFORMS Journal on Computing},
year = {2025},
doi = {10.1287/ijoc.2024.0945},
author = {Johnson Phosavanh and Dmytro Matsypura},
keywords = {degree centrality, betweenness centrality, closeness centrality, group centrality, computational complexity},
note = {Advance online publication.},
abstract = {The centrality of a node is often used to measure its importance to the structure of a network. Some centrality measures can be extended to measure the importance of a path. In this paper, we consider the problem of finding the most central shortest path. We show that the computational complexity of this problem depends on the measure of centrality used and, in the case of degree centrality, whether the network is weighted or not. We develop a polynomial algorithm for the most degree-central shortest path problem with the worst-case running time of $O(|E||V|^2\Delta(G))$, where $|V|$ is the number of vertices, $|E|$ is the number of edges, and $\Delta(G)$ is the maximum degree of the graph. In addition, we show that the same problem is NP-hard on a weighted graph. Furthermore, we show that the problem of finding the most betweenness-central shortest path is solvable in polynomial time, while finding the most closeness-central shortest path is NP-hard, regardless of whether the graph is weighted or not. We also develop an algorithm for finding the most betweenness-central shortest path with a running time of $O(|E|^2|V|^2)$ on unweighted graphs and $O(|E|^2|V|^2 + |V|^2\log(|V|))$ on graphs with positively weighted edges. To conclude our paper, we conduct a numerical study of our algorithms on synthetic and real-world networks and compare our results to the existing literature.},
}

  2. Phosavanh, J. & Oron, D. (2025). Minimizing the number of late jobs and total late work with step-learning. European Journal of Operational Research, 321(3), 734-749. https://doi.org/10.1016/j.ejor.2024.09.042

    We study single-machine scheduling problems with step-learning, where an improvement in processing time is experienced if a job is started at, or after, a job-dependent learning-date. We consider minimizing two functions: the number of late jobs and the total late work, and we show that when at least a common due-date or common learning-date is assumed, the problem is \(\mathcal{NP}\)-hard in the ordinary sense; however, when both are arbitrary, the problem becomes strongly \(\mathcal{NP}\)-hard. For each of the problems where at least one of the dates is assumed to be common, we analyze the structure of an optimal job schedule with and without idle time and propose pseudo-polynomial time dynamic programming algorithms. We also show that the problem of minimizing the weighted number of late jobs with step-learning can be solved with a minor change to the algorithms for the unweighted case. In addition to this, we show that when a common due-date is assumed and no idle time is allowed, the problem of minimizing the total late work is equivalent to that of minimizing the makespan. Furthermore, we provide a more efficient algorithm to solve the problem of minimizing makespan under the assumption of a common learning-date than the one in the existing literature. Lastly, we show that our analysis can also be applied to the case of step-deterioration, where instead, the processing times of jobs increase at a given date.

    @article{PhosavanhOron2025EJOR,
title = {Minimizing the number of late jobs and total late work with step-learning},
journal = {European Journal of Operational Research},
year = {2025},
issn = {0377-2217},
volume = {321},
number = {3},
pages = {734-749},
doi = {10.1016/j.ejor.2024.09.042},
author = {Johnson Phosavanh and Daniel Oron},
keywords = {Scheduling, Single-machine, Step-learning, Dynamic programming},
abstract = {We study single-machine scheduling problems with step-learning, where an improvement in processing time is experienced if a job is started at, or after, a job-dependent learning-date. We consider minimizing two functions: the number of late jobs and the total late work, and we show that when at least a common due-date or common learning-date is assumed, the problem is $\mathcal{NP}$-hard in the ordinary sense; however, when both are arbitrary, the problem becomes strongly $\mathcal{NP}$-hard. For each of the problems where at least one of the dates is assumed to be common, we analyze the structure of an optimal job schedule with and without idle time and propose pseudo-polynomial time dynamic programming algorithms. We also show that the problem of minimizing the weighted number of late jobs with step-learning can be solved with a minor change to the algorithms for the unweighted case. In addition to this, we show that when a common due-date is assumed and no idle time is allowed, the problem of minimizing the total late work is equivalent to that of minimizing the makespan. Furthermore, we provide a more efficient algorithm to solve the problem of minimizing makespan under the assumption of a common learning-date than the one in the existing literature. Lastly, we show that our analysis can also be applied to the case of step-deterioration, where instead, the processing times of jobs increase at a given date.},
}

  3. Phosavanh, J. & Oron, D. (2025). Single-machine two-agent scheduling with a rate-modifying activity and weighted due-date-related functions. Journal of Scheduling. Advance online publication. https://doi.org/10.1007/s10951-025-00853-0

    We analyze two-agent scheduling problems with weighted due-date-related scheduling criteria and an optional rate-modifying activity that, when completed, allows jobs to be completed faster. We start with the single-agent problem of minimizing the total weighted late work and then extend the results over to two-agent problems involving combinations of the weighted number of late jobs and the total weighted late work. We examine the properties of optimal schedules and provide efficient pseudo-polynomial time algorithms to solve these problems.

    @article{PhosavanhOron2025JoS,
title = {Single-machine two-agent scheduling with a rate-modifying activity and weighted due-date-related functions},
journal = {Journal of Scheduling},
year = {2025},
doi = {10.1007/s10951-025-00853-0},
author = {Johnson Phosavanh and Daniel Oron},
keywords = {Two-agent scheduling, Single-machine, Rate-modifying activity, Dynamic programming},
note = {Advance online publication.},
abstract = {We analyze two-agent scheduling problems with weighted due-date-related scheduling criteria and an optional rate-modifying activity that, when completed, allows jobs to be completed faster. We start with the single-agent problem of minimizing the total weighted late work and then extend the results over to two-agent problems involving combinations of the weighted number of late jobs and the total weighted late work. We examine the properties of optimal schedules and provide efficient pseudo-polynomial time algorithms to solve these problems.},
}

  4. Phosavanh, J. & Oron, D. (2024). Two-agent single-machine scheduling with a rate-modifying activity. European Journal of Operational Research, 312(3), 866-876. https://doi.org/10.1016/j.ejor.2023.08.002

    We study single-machine scheduling problems involving a rate-modifying activity and two competing agents with due-date-related functions. Classical scheduling models assume that job processing times remain constant over time; however, in real-world settings, processing times may change due to factors such as technological upgrades or machine maintenance. We complement this with the notion of multiple independent agents competing over the use of a shared resource, each with their own motives. These considerations allow us to model the upcoming trend of the sharing economy, where resources are shared amongst independent competitors in the market. We aim to model these scenarios by considering a variety of scheduling criteria for each agent, including the makespan, the number of late jobs, and the total late work. To account for the change in processing times, we consider an optional rate-modifying activity that once completed, results in a reduction in subsequent job processing times. We show that problems involving the total late work are binary \(\mathcal{NP}\)-hard and propose efficient pseudo-polynomial dynamic programming algorithms for solving these problems. We also show that the remaining problems are solvable in polynomial time.

    @article{PhosavanhOron2024,
title = {Two-agent single-machine scheduling with a rate-modifying activity},
journal = {European Journal of Operational Research},
year = {2024},
volume = {312},
pages = {866-876},
number = {3},
issn = {0377-2217},
doi = {10.1016/j.ejor.2023.08.002},
author = {Johnson Phosavanh and Daniel Oron},
keywords = {Scheduling, Single machine, Two-agents, Dynamic programming},
abstract = {We study single-machine scheduling problems involving a rate-modifying activity and two competing agents with due-date-related functions. Classical scheduling models assume that job processing times remain constant over time; however, in real-world settings, processing times may change due to factors such as technological upgrades or machine maintenance. We complement this with the notion of multiple independent agents competing over the use of a shared resource, each with their own motives. These considerations allow us to model the upcoming trend of the sharing economy, where resources are shared amongst independent competitors in the market. We aim to model these scenarios by considering a variety of scheduling criteria for each agent, including the makespan, the number of late jobs, and the total late work. To account for the change in processing times, we consider an optional rate-modifying activity that once completed, results in a reduction in subsequent job processing times. We show that problems involving the total late work are binary $\mathcal{NP}$-hard and propose efficient pseudo-polynomial dynamic programming algorithms for solving these problems. We also show that the remaining problems are solvable in polynomial time.},
}

Articles under review

  1. Phosavanh J. & Oron, D. (2026). Minimizing total weighted late work with step-learning on a single machine. Submitted to Discrete Applied Mathematics (3rd round R&R).

    We study single-machine scheduling problems with step-learning to minimize the total weighted late work. Step-learning is a mechanism that allows jobs to be completed more efficiently if started after a job-dependent learning-date. We show that this problem is strongly \(\mathcal{NP}\)-hard when both learning-dates and due-dates are arbitrary, but when at least one is assumed to be the same for all jobs, the problem is \(\mathcal{NP}\)-hard in the ordinary sense, and we provide pseudo-polynomial algorithms for these cases.

Conferences

  1. Phosavanh J., Oron, D. (2025, November 26 – 28). Single-machine scheduling with cooperative agents and nondisjoint job sets. Workshop on Optimisation, Metric Bounds, Approximation and Transversality (WOMBAT), Brisbane, QLD, Australia.
  2. Phosavanh J., Oron, D. (2025, October 26 – 29). Single-machine scheduling with cooperative agents and nondisjoint job sets. 2025 INFORMS Annual Meeting, Atlanta, GA, United States of America.
  3. Phosavanh J., Oron, D. (2025, June 22 – 25). Single-machine scheduling with cooperative agents and nondisjoint job sets. 34th European Conference on Operational Research (EURO 2025), Leeds, United Kingdom.
  4. Phosavanh J., Oron, D. (2024, December 4 – 6). Minimizing the number of late jobs and total late work with step-learning. Workshop on Optimisation, Metric Bounds, Approximation and Transversality (WOMBAT), Sydney, NSW, Australia.
  5. Phosavanh J., Oron, D. (2024, October 20 – 23). Minimizing the number of late jobs and total late work with step-learning. 2024 INFORMS Annual Meeting, Seattle, WA, United States of America.
  6. Phosavanh J., Oron, D. (2024, June 30 – July 3). Minimizing the number of late jobs and total late work with step-learning. 33rd European Conference on Operational Research (EURO 2024), Copenhagen, Denmark.
  7. Phosavanh J., Matsypura, D. (2023, December 11 – 16). Finding the most central shortest path in a graph. Joint Workshop on Optimisation, Metric Bounds, Approximation and Transversality (WOMBAT) and Workshop on the Intersections of Computation and Optimisation (WICO), Sydney, NSW, Australia.
  8. Phosavanh J., Matsypura, D. (2023, October 15 – 18). Finding the most central shortest path in a graph. 2023 INFORMS Annual Meeting, Phoenix, AZ, United States of America.
  9. Phosavanh J., Oron, D. (2023, June 5 – 6). Single-machine scheduling with two competing agents and rate-modifying activities with weighted due-date related functions. The Fourth International Workshop on Dynamic Scheduling Problems (IWDSP 2023), Winterthur, Switzerland.
  10. Phosavanh J., Oron, D. (2022, December 6 – 9). Two-agent single-machine scheduling with a rate-modifying activity. 66th Annual Meeting of the Australian Mathematical Society (AustMS), Sydney, NSW, Australia.

Teaching

The University of Sydney

  • QBUS1040: Foundations of Business Analytics
    • Coordinator & Lecturer: Semester 1, 2025 – Semester 2, 2025
    • Head tutor: Semester 1, 2022 – Semester 2, 2024
    • Tutor: Semester 2, 2021
    • Lab demonstrator: Semester 1, 2019 – Semester 1, 2021
  • QBUS2310: Management Science
    • Head tutor: Semester 1, 2022 – Semester 2, 2024
  • QBUS6820: Prescriptive Analytics: From Data to Decision
    • Head tutor: Semester 1, 2023
  • DATA1001: Foundations of Data Science
    • Lab demonstrator: Semester 1, 2020 – Semester 2, 2020
  • MATH1005: Statistical Thinking with Data
    • Lab demonstrator: Semester 2, 2020

Scholarships & Awards

Research

  • Business School Post-Submission Award, 2026.
  • Enhanced Business School Research Scholarship, 2022 – 2025.
  • Discipline of Business Analytics Student Poster Prize Winner, 2025.
  • Postgraduate Research Support Scheme, 2025.
  • Research Travel Support Scheme, 2025.
  • Discipline of Business Analytics Student Paper Prize Winner, 2024.
  • Postgraduate Research Support Scheme, 2024.
  • Research Travel Support Scheme, 2024.
  • Research Travel Support Scheme, 2023.
  • The Westbrook and Jessie Anstice Honours Scholarship in Business, 2021.
  • Denison Research Scholarship, 2019 – 2020.

Teaching

  • 2024 Dean’s Award for Feedback for Teaching (FFT).
    • Awarded in recognition of outstanding performance of an individual instructor demonstrating and reflecting upon exceptional teaching.
  • Feedback for Teaching (FFT) Student Survey Award for Teaching.
    • Awarded in recognition of individual instructors based on high overall evaluations from students on the FFT:
      • QBUS1040, Semester 1, 2024.
      • QBUS2310, Semester 1, 2024.
      • QBUS1040, Semester 2, 2023.
  • 2022 Discipline of Business Analytics Teaching Excellence Award.
    • Awarded in recognition of outstanding achievement in teaching within the Discipline of Business Analytics.

Academic

  • University of Sydney Academic Merit Prize, 2021.
  • Dean’s List of Excellence in Academic Performance, 2021.
  • University of Sydney Academic Merit Prize, 2020.
  • Dean’s List of Excellence in Academic Performance, 2020.
  • University of Sydney Academic Merit Prize, 2019.
  • Discipline of Business Analytics Prize in 2nd year Quantitative Business, 2019.
  • Tim Brown Prize No 1 for Intermediate Statistics, 2019.
  • Dean’s List of Excellence in Academic Performance, 2019.
  • Dean’s List of Excellence in Academic Performance, 2018.