Natasha Shakhlevich

Publications

• "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 , (in press)
• "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, 2017
• "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, 2016
• "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