Research Activity -
Algorithms and Complexity

Natasha Shakhlevich

Natasha Shakhlevich's Papers

·         “Parallel Batch Scheduling of Equal-Length Jobs with Release and Due Dates”
A. Condotta, S. Knust, N.V. Shakhlevich
Journal of Scheduling 13, pages 463-477, 2010 DOI 10.1007/s10951-010-0176-y

·         “A Polynomial-Time Algorithm for a Flow-Shop Batching Problem with Equal-Length Operations”
P. Brucker, N.V. Shakhlevich,
Journal of Scheduling (accepted) DOI 10.1007/s10951-009-0150-8

·         “Inverse Scheduling: Two Machine Flow Shop Problem”
P. Brucker, N.V. Shakhlevich,
Journal of Scheduling (accepted) DOI 10.1007/s10951-010-0168-y

·          “Inverse Scheduling with Maximum Lateness Objective”
P. Brucker, N.V. Shakhlevich,
Journal of Scheduling 12, pages 475–488, 2009 DOI: 10.1007/s10951-009-0117-9

·         “Single Machine Scheduling with Controllable Processing Times by Submodular Optimization”
N.V. Shakhlevich, A. Shioura, V.A. Strusevich,
International Journal of Foundations of Computer Science 20, 247-269, 2009, DOI: 10.1142/S0129054109006541

·         “Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach”
N.V. Shakhlevich, A. Shioura, V.A. Strusevich,
Proceedings of the 16th Annual European Symposium on Algorithms (ESA 2008),
Lecture Notes in Computer Science  5193, pages 756-767, 2008 doi.org/10.1007/978-3-540-87744-8_63

·         “Preemptive scheduling on uniform parallel machines with controllable job processing times”
N.V. Shakhlevich, V.A. Strusevich,
Algorithmica 51, pages 451-473, 2008 doi:10.1007/s00453-007-9091-9

·         "Two-machine open shop problem with controllable processing times"
T.C.E. Cheng, N.V. Shakhlevich,
Discrete Optimization 4, pages 175-184, 2007 doi:10.1016/j.disopt.2006.10.010

·         "Single machine scheduling with controllable release and processing parameters"
N.V. Shakhlevich, V.A. Strusevich,
Discrete Applied Mathematics 154, pages 2178-2199, 2006 doi:10.1016/j.dam.2005.04.014

·         "Scheduling with controllable release dates and processing times: Makespan minimization"
T.C.E. Cheng, M.Y. Kovalyov, N.V. Shakhlevich,
European Journal of Operational Research 175, 751-768, 2006 doi:10.1016/j.ejor.2005.06.021

·         "Scheduling with controllable release dates and processing times: Total completion time minimization"
T.C.E. Cheng, M.Y. Kovalyov, N.V. Shakhlevich,
European Journal of Operational Research 175, 769-781, 2006 doi:10.1016/j.ejor.2005.06.072 

·         "Unit-time open-shop scheduling problems with symmetric objective functions"
N.V. Shakhlevich,
4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies 3, 117-131, 2005 doi:10.1007/s10288-005-0061-2

·         "Pre-emptive scheduling problems with controllable processing times"
N.V. Shakhlevich, V.A. Strusevich,
Journal of Scheduling 8, pages 233-253, 2005 doi:10.1007/s10951-005-6813-1

·         "Minimizing nondecreasing separable objective functions for the unit-time open shop scheduling problem"
T.C.E. Cheng, N.V. Shakhlevich
European Journal of Operational Research 165, pages 444-456, 2005 doi:10.1016/j.ejor.2004.04.014
short version Proceedings of the 8th International Workshop on Project Management and Scheduling (PMS'02), pages 96-99, 2002.

·         "Complexity results for shop problems with transportation delays"
P. Brucker, S. Knust, T.C.E. Cheng, N.V. Shakhlevich
Annals of Operations Research 129, pages 81-106, 2004.

·         "Single machine scheduling of unit-time jobs with controllable release dates
T.C.E. Cheng, N.V. Shakhlevich
Journal of Global Optimization 27, pages 293 - 311, 2003.

·         "Scheduling with controllable release dates and processing times"
T.C.E. Cheng, M.Y. Kovalyov, N.V. Shakhlevich
Report 2002.18, School of Computing, University of Leeds, 2002
short version Proceedings of the Fifth Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'01), Aussois, France, 2001.

·         "Three-machine shop scheduling with partially ordered processing routes"
V.A. Strusevich, I.G. Drobouchevitch, N.V. Shakhlevich
Journal of the Operational Research Society 53, pages 574-582, 2002.

·         "Common due date assignment and scheduling with ready times"
T.C.E. Cheng, Z.-L. Chen, N.V. Shakhlevich
Computers and Operations Research 29, pages 1957 - 1967, 2002.

·         "Complexity of mixed shop scheduling problems: a survey"
N.V. Shakhlevich, Y.N. Sotskov, F. Werner
European Journal of Operational Research 120, pages 343 - 351, 2000.

·         "Proportionate flow shop with controllable processing times"
T.C.E. Cheng, N.V. Shakhlevich
Journal of Scheduling 2, pages 253 - 265, 1999.

·         "Shop-scheduling problems with fixed and non-fixed machine orders of the jobs"
N.V. Shakhlevich, Y.N. Sotskov, F. Werner
Annals of Operations Research 92, pages 281 - 304, 1999.

·         "On the solution region for certain scheduling problems with preemption"
H. Bräsel, N.V. Shakhlevich
Annals of Operations Research 83, pages 1 - 21, 1998.

·         "Minimizing total weighted completion time in a proportionate flow-shop"
N.V. Shakhlevich, H. Hoogeveen, M. Pinedo
Journal of Scheduling 1, pages 157 - 168, 1998.

·         "Adaptive scheduling algorithm based on mixed graph model"
N.V. Shakhlevich, Y.N. Sotskov, F. Werner
IEE Proceedings on Control Theory and Applications 143, pages 9 - 16, 1996.

·         "A heuristic decomposition algorithm for scheduling problems on mixed graphs"
K. Krüger, N.V. Shakhlevich, Y.N. Sotskov, F. Werner
Journal of the Operational Research Society 46, pages 1481 -1497, 1995.

·         "NP-hardness of shop-scheduling problems with three jobs"
Y.N. Sotskov, N.V. Shakhlevich
Discrete Applied Mathematics 59, pages 237 - 266, 1995.

·         "Scheduling two jobs with fixed and non-fixed routes"
N.V. Shakhlevich, Y.N. Sotskov
Computing 52, pages 17 - 30, 1994.

·         "Optimal job-shop scheduling with two jobs in systems with unrestricted paths"
V.A. Strusevich, N.V. Shakhlevich
Computational Mathematics and Mathematical Physics 33, pages 593 - 601, 1993.

·         "Two machine open shop scheduling problem to minimize an arbitrary machine usage penalty function"
N.V. Shakhlevich, V.A. Strusevich
European Journal of Operational Research 70, pages 391 - 404, 1993.

·         "Optimal scheduling two jobs in an open-shop"
V.A. Strusevich, N.V. Shakhlevich
Zhurnal Vychislitel'noy Matematiki i Matematicheskoy Fiziki 33, pages 659 - 670, 1993 (In Russian).

·         "Adaptive algorithm for minimizing total request servicing time by serial devices"
Y.N. Sotskov, N.V. Shakhlevich
Soviet Journal of Computer and Systems Sciences 29, pages 43 - 47, 1991.

·         "An adaptive algorithm for scheduling jobs in a job shop"
Y.N. Sotskov, N.V. Shakhlevich
Izvestiya Akademii Nauk SSSR. Tekhnicheskaya Kibernetika 6, 137 - 142, 1990 (In Russian).

·         "NP-hardness of scheduling problems of with three jobs"
Y.N. Sotskov, N.V. Shakhlevich
Vestsi Akademii Navuk BSSR. Seria Fizika-Matematychnykh Navuk 4, pages 96 - 101, 1990 (In Russian).

ns@comp.leeds.ac.uk

© School of Computing University of Leeds 1998-2008	Contact Web Editor	Last modified 19 Sep 2010