# Natasha Shakhlevich

- Position
- Senior Lecturer

## Publications

- "Generalizing Horn’s conditions for preemptive scheduling on identical parallel machines via network flow techniques"

Shioura, A., Strusevich, V.A., and Shakhlevich, N.V.

*Networks*(accepted). - "Affinity-aware resource provisioning for long-running applications in shared clusters"

Mommessin, C., Yang, R., Shakhlevich, N.V., Sun, X., Kumar, S., Xiao, J., and Xu, J.

*Journal of Parallel and Distributed Computing,***177**, 1–16, 2023 - "Preemptive scheduling of parallel jobs of two sizes with controllable processing times"

Shioura, A., Strusevich, V.A., and Shakhlevich, N.V.

*Journal of Scheduling*(in press). - "Scheduling divisible loads with time and cost constraints"

Drozdowski, M., Shakhlevich, N.V.

*Journal of Scheduling,***24**, 507-521, 2021 - "Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost"

Shioura, A., Shakhlevich, N.V., and Strusevich, V.A.,

Journal of Global Optimization,**76**, 471-490. - "Shop scheduling problems with pliable jobs"

Knust, S., Shakhlevich, N.V., Waldherr, S. and Weiß, C.

*Journal of Scheduling***22**, 635-661, 2019 - "Models and algorithms for energy-efficient scheduling with immediate start of jobs"

Shioura, A., Shakhlevich, N.V., Strusevich, V.A., B. Primas

*Journal of Scheduling*,**21**, 505-516, 2018 - "Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches"

Shioura, A., Shakhlevich, N.V., and Strusevich, V.A.,

*European Journal of Operational Research (invited review)*,**266**, 795-818, 2018 - "Machine speed scaling by adapting methods for convex optimization with submodular constraints"

Shioura, A., Shakhlevich, N.V., and Strusevich, V.A.,

*INFORMS Journal on Computing*,**29**, 724-736, 2017 - "Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines"

Shioura, A., Shakhlevich, N.V., and Strusevich, V.A.,

*INFORMS Journal on Computing*,**28**, 148-161, 2016 - "Handling scheduling problems with controllable parameters by methods of submodular optimization"

Shioura, A., Shakhlevich, N.V., and Strusevich, V.A.,

*Lecture Notes in Computer Science*,**9869**, 74-90, 2016 - "The assignment problem with nearly Monge arrays and incompatible partner indices"

Weiss, C., Knust, S., Shakhlevich, N.V., Waldherr, S.,

*Discrete Applied Mathematics*,**211**, 183-203, 2016 - "Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines"

Brucker, P., Shakhlevich, N.V.,

*Journal of Scheduling***19**, 659-685, 2016 - "Open shop scheduling with synchronization"

Weiss, C., Waldherr, S., Knust, S., Shakhlevich, N.V.,

*Journal of Scheduling***20**, 557-581, 2017 - "Complexity results for storage loading problems with stacking constraints"

Bruns, F., Knust, S., and Shakhlevich, N.V. ,

*European Journal of Operational Research***249**, 1074-1081, 2016 - "Resource boxing: converting realistic cloud task utilization patterns for theoretical scheduling"

Primas, B., Garraghan, P., Djemame, K., and Shakhlevich, N.V.

in*UCC'2016 Proceedings of the 9th International Conference on Utility and Cloud Computing,*ACM, New York, 138-147, 2016 - "Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times"

Shioura, A., Shakhlevich, N.V., and Strusevich, V.A.,

*Mathematical Programming, Ser. A***153**, 495-534, 2015 - "Scheduling patient appointments via multilevel template: a case study in chemotherapy"

Condotta, A., Shakhlevich, N.V.

*Journal of Operations Research for Health Care***3**, 129-144, 2014 - "Scheduling bag-of-tasks applications to optimize computation time and cost"

Grekioti, A., and Shakhlevich, N.V.

Proceedings of the 10th International Conference on Parallel Processing and Applied Mathematics (PPAM 2013)

*Lecture Notes in Computer Science***8384-8385**, 3-12, 2014. - "Scheduling divisible loads to optimize the computation time and cost"

Shakhlevich, N.V.

Proceedings of the 10th International Conference Economics of Grids, Clouds, Systems, and Services (GECON 2013)

*Lecture Notes in Computer Science***8193**, 138-148, 2013. - "A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines"

Shioura, A., Shakhlevich, N.V., and Strusevich, V.A.

*SIAM Journal on Discrete Mathematics***27**, 186-204, 2013. - "A note on reverse scheduling with maximum lateness objective"

Li, S.S., Brucker, P., Ng, C.T., Cheng, T.C.E., Shakhlevich, N.V., and Yuan, J.J.

*Journal of Scheduling***16**, 417-422, 2013. - "Minimising the number of gap-zeros in binary matrices"

Chakhlevitch, K., Glass, C.A., and Shakhlevich, N.V.

*European Journal of Operational Research***229**, 48-58, 2013. - "Tabu search and lower bounds for a combined production-transportation problem"

Condotta, A., Knust., S., Meier, D., Shakhlevich, N.V.

*Computers & Operations Research***40**, 886-900, 2013. - "Scheduling coupled-operation jobs with unit-time jobs"

Condotta, A., Shakhlevich, N.V.

*Discrete Applied Mathematics***160**, 2370-2388, 2012. - "A polynomial-time algorithm for a flow-shop batching problem with equal-length operations"

Brucker, P., and Shakhlevich, N.V.

*Journal of Scheduling***14**, 371-389, 2011. - "Inverse scheduling: two machine flow shop problem"

Brucker, P., and Shakhlevich, N.V.

*Journal of Scheduling***14**, 239-256, 2011. - "Parallel batch scheduling of equal-length jobs with release and due dates"

Condotta, A., Knust., S., Shakhlevich, N.V.

*Journal of Scheduling***13**, 463-477, 2010. - "Inverse scheduling with maximum lateness objective"

Brucker, P., and Shakhlevich, N.V.

*Journal of Scheduling***12**, 475-488, 2009. - "Single machine scheduling with controllable processing times by submodular optimization"

Shakhlevich, N.V., Shioura, A., and Strusevich, V.A.

*International Journal of Foundations of Computer Science***20**, 247-269, 2009. - "Preemptive scheduling on uniform parallel machines with controllable job processing times"

Shakhlevich, N.V., and Strusevich, V.A.

*Algorithmica***51**, 451-473, 2008. - "Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times: a polymatroid optimization approach"

Shakhlevich, N.V., Shioura, A., and Strusevich, V.A.

Proceedings of the 16th Annual European Symposium on Algorithms (ESA 2008)

*Lecture Notes in Computer Science***5193**, 756-767, 2008. - "Two-machine open shop problem with controllable processing times"

Cheng, T.C.E., and Shakhlevich, N.V.

*Discrete Optimization***4**, 175-184, 2007. - "Single machine scheduling with controllable release and processing parameters"

Shakhlevich, N.V., and Strusevich, V.A.

*Discrete Applied Mathematics***154**, 2178-2199, 2006. - "Scheduling with controllable release dates and processing times: makespan minimization"

Cheng, T.C.E., Kovalyov, M.Y., and Shakhlevich, N.V.

*European Journal of Operational Research***175**, 751-768, 2006. - "Scheduling with controllable release dates and processing times: total completion time minimization"

Cheng, T.C.E., Kovalyov, M.Y., and Shakhlevich, N.V.

*European Journal of Operational Research***175**, 769-781, 2006. - "Open-shop unit-time scheduling problems with symmetric objective functions"

Shakhlevich, N.V.

*4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies***3**, 117-131, 2005. - "Preemptive scheduling problems with controllable processing times"

Shakhlevich, N.V., and Strusevich, V.A.

*Journal of Scheduling***8**, 233-253, 2005. - "Minimizing nondecreasing separable objective functions for the unit-time open shop scheduling problem"

Cheng, T.C.E., and Shakhlevich, N.V.

*European Journal of Operational Research***165**, 444-456, 2005. - "Complexity results for flow-shop and open-shop scheduling problems with transportation delays"

Brucker, P., Knust, S., Cheng, T.C.E., and Shakhlevich, N.V.

*Annals of Operations Research***129**, 81-106, 2004. - Single machine scheduling of unit-time jobs with controllable release dates

Cheng, T.C.E., and Shakhlevich, N.V.

*Journal of Global Optimization***27**, 293-311, 2003. - "Three-machine shop scheduling with partially ordered processing routes"

Strusevich, V.A., Drobouchevitch, I.G., and Shakhlevich, N.V.

*Journal of the Operational Research Society***53**, 574-582, 2002. - "Common due date assignment and scheduling with ready times"

Cheng, T.C.E., Chen, Z.-L., and Shakhlevich, N.V.

*Computers and Operations Research***29**, 1957-1967, 2002. - "Complexity of mixed shop scheduling problems: a survey"

Shakhlevich, N.V., Sotskov, Y.N. and Werner, F.

*European Journal of Operational Research***120**, 343-351, 2000. - "Proportionate flow shop with controllable processing times"

Cheng, T.C.E., and Shakhlevich, N.V.

*Journal of Scheduling***2**, 253-265, 1999. - "Shop-scheduling problems with fixed and non-fixed machine orders of the jobs"

Shakhlevich, N.V., Sotskov, Y.N. and Werner, F.

*Annals of Operations Research***92**, 281-304, 1999. - "On the solution region for certain scheduling problems with preemption"

Braesel, H., and Shakhlevich, N.V.

*Annals of Operations Research***83**, 1-21, 1998. - "Minimizing total weighted completion time in a proportionate flow-shop"

Shakhlevich, N.V., Hoogeveen, H., Pinedo, M.

*Journal of Scheduling***1**, 157-168, 1998. - "Adaptive scheduling algorithm based on mixed graph model"

Shakhlevich, N.V., Sotskov, Y.N. and Werner, F.

*IEE Proceedings on Control Theory and Applications***143**, 9-16, 1996. - "A heuristic decomposition algorithm for scheduling problems on mixed graphs"

Krueger, K., Shakhlevich, N.V., Sotskov, Y.N. and Werner, F.

*Journal of the Operational Research Society***46**, 1481 -1497, 1995. - "NP-hardness of shop-scheduling problems with three jobs"

Shakhlevich, N.V., and Sotskov, Y.N.

*Discrete Applied Mathematics***59**, 237-266, 1995. - "Scheduling two jobs with fixed and non-fixed routes"

Shakhlevich, N.V., and Sotskov, Y.N.

*Computing***52**, 17-30, 1994. - "Adaptive approach in production scheduling based on the mixed graph model"

Sotskov, Y.N., and Shakhlevich, N.V.

*Proceedings of the 2nd International Conference on Intelligent Systems Engineering, Hamburg,***395**, 413-418, 1994. - "Optimal job-shop scheduling with two jobs in systems with unrestricted paths"

Strusevich, V.A., and Shakhlevich, N.V.

*Computational Mathematics and Mathematical Physics***33**, 593-601, 1993. - "Two machine open shop scheduling problem to minimize an arbitrary machine usage penalty function"

Shakhlevich, N.V., and Strusevich, V.A.

*European Journal of Operational Research***70**, 391-404, 1993. - "Optimal scheduling two jobs in an open-shop"

Strusevich, V.A., and Shakhlevich, N.V.

*Zhurnal Vychislitel'noy Matematiki i Matematicheskoy Fiziki***33**, 659-670, 1993 (In Russian). - "Adaptive algorithm for minimizing total request servicing time by serial devices"

Sotskov, Y.N., and Shakhlevich, N.V.

*Soviet Journal of Computer and Systems Sciences***29**, 43-47, 1991. - "An adaptive algorithm for scheduling jobs in a job shop"

Sotskov, Y.N., and Shakhlevich, N.V.

*Izvestiya Akademii Nauk SSSR. Tekhnicheskaya Kibernetika***6**, 137-142, 1990 (In Russian). - "NP-hardness of scheduling problems of with three jobs"

Sotskov, Y.N., and Shakhlevich, N.V.

*Vestsi Akademii Navuk BSSR. Seria Fizika-Matematychnykh Navuk***4**, 96-101, 1990 (In Russian).

### Preprints

- "Machine speed scaling by adapting methods for convex optimization with submodular

constraints"

Shioura, A., Shakhlevich, N.V., Strusevich, V.A., 2015 - "Scheduling imprecise computation tasks on parallel machines to minimize

linear and non-linear error penalties: Reviews, links and improvements"

Shioura, A., Shakhlevich, N.V., Strusevich, V.A., 2015 - "Speed scaling for scheduling problems with immediate start of jobs"

Shioura, A., Shakhlevich, N.V., Strusevich, V.A., Primas, B. 2015 - "Time/Cost optimization in Grid scheduling: analytical results and practical implications"

Armstrong, A., Djemame, K., and Shakhlevich, N.V., 2014