# Associate Professor Yakov Zinder

**Associate Professor,**School of Mathematical Sciences

**Associate Member,**Quantitative Finance Research Centre

MSc (Gorky), PhD (CC USSR AcadSc)

**Phone**

+61 2 9514 2279

**Room**

CB01.15.31

## Chapters

Zinder, Y. & Do, V. 2005, 'Scheduling UET tasks on two parallel machines with the criteria of makespan and total completion time' in Kendall, G., Burke, E., Petrocic, S. & Gendreau, M. (eds),

*Multidisciplinary Scheduling: Theory and applications*, Springer, USA, pp. 83-109. Two extensions of the classical scheduling model with two parallel identical machines and a partially ordered set of unit execution time tasks are considered. It is well known that the Coffman-Graham algorithm constructs for this model a so-called ideal schedule: that is, a schedule which is optimal for both makespan and total completion time criteria simultaneously. The question of the existence of such a schedule for the extension of this model, where each task has a release time, has remained open over seneral decades. The paper gives a positive answer to this question and presents the corresponding polynormal-time algorithm.Another straightforward generalisation of the considered classcial model is obtained by the introduction of multiprocessor tasks. It is shown that, despite the fact tha a slightly modified Coffman-Graham algorithm solves the makespan problem with multiprocessor tasks for arbirtary precedence constraints, generally an ideal schedule does not exist and the problem with the criterion of total completion time turns out to be NP-hard ithe strong sense even for in-trees.

Zinder, Y. & Shkurba, V. 2002, 'Scheduling Theory' in Michiel Hazewinkel (ed),

*Encyclopaedia of Mathematics*, Springer, Amsterdam, pp. 209-210.## Conferences

Zinder, Y., Nicorovici, N.A. & Langtry, T. 2011, 'Mathematica based platform for self-paced learning',

*Proceedings of the 10th International Conference on Technology in Mathematics Teaching (ICTMT10)*, University of Portsmouth, United Kingdom, pp. 203-208. One of the major challenges in teaching applied mathematics is the large amount of calculation involved in many practical mathematical methods. On one hand, mastering these methods requires students to gain experience in performing all steps of a calculation. This experience is crucial for gaining an understanding of the methods, their capabilities and limitations, and cannot be replaced by black box type commercial software which simply displays the results of calculations and gives no insight into the nature of the operations performed. On the other hand, the calculations involved in many modern mathematical methods are tedious and time consuming with fatal results caused by even minor computational mistakes. The advent of computer algebra systems such as Mathematica opened new horizons in teaching mathematics. The ability to perform symbolic calculations in combination with powerful graphics and programming capabilities makes it possible to develop software that provides students with the opportunity for step by step exploration of mathematical procedures. We present the results of an ongoing research project aimed at the development of a Mathematica based platform which allows academics to develop software for self-paced learning.

Fung, J., Singh, G. & Zinder, Y. 2010, 'Capacity planning for a coal supply chain',

*The 2nd International Conference on Logistics and Transport*, Lincoln University, New Zealand. Zinder, Y., Memar, J. & Singh, G. 2010, 'Discrete Optimization with Polynomially Detectable Boundaries and Restricted Level Sets',

*COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PT 1*, SPRINGER-VERLAG BERLIN, pp. 142-156. Zinder, Y., Nicorovici, N. & Langtry, T. 2010, 'MATHEMATICA BASED PLATFORM FOR SELF-PACED LEARNING',

*EDULEARN10: INTERNATIONAL CONFERENCE ON EDUCATION AND NEW LEARNING TECHNOLOGIES*, IATED-INT ASSOC TECHNOLOGY EDUCATION A& DEVELOPMENT, pp. 323-330. Zinder, Y. & Walker, S.J. 2009, 'Scheduling flexible multiprocessor tasks on parallel machines',

*9th Workshop on Models and Algorithms for Planning and Scheduling Problems*, Abbey Rolduc, Netherlands, pp. 23-25. We consider the following scheduling problem. A ?nite set of tasks (jobs, operations) N = {1, 2, . . . , n} is to be processed on m > 1 identical parallel machines (processors). The processing of tasks begins at time t = 0. Each machine can process only one task at a time. The order in which tasks can be processed is restricted by a transitive, antire?exive and antisymmetric relation on N, called precedence constraints. If task j precedes task g, denoted j ? g, t h e n task g can not be processed until task j has been completed. In order to be completed, a task j requires pj units of processing time. At di?erent points in time a task may be processed by a di?erent number of machines. The maximum number of machines which can process task j simultaneously is 1 = uj = m. The number of machines processing a task can change at any point in time without penalty

Zinder, Y., Singh, G., Su, B. & Sorli, R.M. 2007, 'Scheduling UET-UCT tasks: branch-and-bound search in the priority space',

*7th International conference on optimisation: techniques and applications (ICOTA7)*, Universal Academy Press Inc, Kobe, Japan, pp. 1-12. The paper is concerned iwth the problem of scheduling partially ordered unit execution time tasks on parallel processors with unit communication delays and release times. Two criteria are considered the maximum lateness and its particular case, the makespan. This problem plays an important role in scheduling theoery and was originally inspired by the applications to the multi-processor computer systems

Zinder, Y., Singh, G. & Weiskircher, R. 2006, 'A new method of scheduling UET tasks on parallel machines',

*Lecture Notes in Engineering and Computer Science*, pp. 796-801. The paper describes a new method of scheduling partially ordered unit execution time tasks on parallel machines. The goal is to minimize the largest completion time. It is well known that this scheduling problem is NP-hard in the strong sense, and the commonly used approach, guaranteeing the construction of an optimal schedule, is the branch-and-bound method. We compare the conventional branch-and- bound method and our new method, described in this paper, by means of computational experiments.

Zinder, Y. 2005, 'Scheduling UET tasks on parallel machines: strength of priority algorithms',

*Proceedings of the 18th National Conference of the Australian Society for OPerations Research and the 11th Australian Optimisation Day*, Western Australian Centre of Excellence in Industrial Optimisation, Curtin University of Technology, Perth, Australia, pp. 186-191. The paper is concerned with the problem of shceduling a partially ordered set of unit execution time tasks on parallel identical machines in ordered to minimise the criterion of maximum lateness which plays one of the central roles in scheduling theory. It is well known that the considered scheduling problem is NP-hard in the strong sense, and therefore various polynormial-time algorithms, developed for this problem are usually schracterised by their worst-case performance. For a broad class of scheduling algorithms, the paper introduces a notion of a strength, characterising their worst-case performance and within this formal framework gives a positive answer to the question of the existence of a strongest algorithm i.e. agorithm with the best worst-case performance.

Hanen, C. & Zinder, Y. 2005, 'The worst-case analysis of the Garey-Johnson algorithm for preemptive tasks on m processors',

*Proceedings of the 2nd multidisciplinary international conference on scheduling: theory and applications*, Stern School of Business, New York University, New York, USA, pp. 453-470. The classical Garey-Johnson algorithm was originally developed for the maximum lateness problem with two parallel identical machines and partially ordered unit execution time tasks, but the main idea of the Garey-Johnson algorithm is applicable far beyond the confines of this particular problem. This paper analyses the worst-case performance of a generalisation of the Garey-Johnson algorithm for the problem with arbitrary number of machines and partially ordered tasks allowing preemptions. The presented performance guarantee is the nest among all currently known for this problem.

Hanen, C. & Zinder, Y. 2005, 'Scheduling UET-UCT task systems under the out-forest precedence constraints',

*Proceedings of the 2nd multidisciplinary international conference on scheduling: theory and applications*, New York University, New York, USA, pp. 445-452. This paper is concerend with two problems of schduling unit execution time task systems on parallel identical processors wuth unit communication delays and precedence constraints in the form of an out-forest. One problem is the maximum lateness problem with different release times. To the authors' knowledge the presented worst-case analysis of an approximation algorithm, generalising the idea of the classical Garey-Johnson algorithm, is the first result of this type for models with communication delays and different release times, and provides the best currently known performace guarantee for problems with communucation delays and precedence constraints in the form of out-forest. The paper also presents an iterative algorithm, constructing an optimal schedule, for a two-processor system, for the criterion of total completion time, among optimal schedules for the criterion of maximum lateness.

Zinder, Y. & Singh, G. 2004, 'Preemptive scheduling on parallel processors with due dates',

*Proceedings of the International Symposium on Scheduling 2004*, Japan Society of Mechanical Engineers, Tokyo, Japan, pp. 100-103. Hanen, C. & Zinder, Y. 2002, 'The worst-case analysis of the Garey-Johnson algorithm',

*8th International Workshop on Project Management and Scheduling*, The European Journal of Operational Research, Spain. The Garey-Johnson algorithm is one of only two known polynomial-time algorithms allowing to construct an optimal schedule for the maximum lateness problem with unit execution tasks, two parallel identical processors, precedence constraints and release times. The paper is concerned with the worst-case analysis of a generalisation of the Garey-Johnson algorithm for the case of arbitrary number of processors. We prove that for even number of processors the algorithm is characterised by the best currently known performance guarantee, whereas for odd number of processors it is less competitive.

Singh, G. & Zinder, Y. 2000, 'Worst-case performance of critical path type algorithms',

*15th National Conference of Australian Society for Operations Research*, Australian Society for Operations Research, Australia, pp. 383-399. The critical path method remains one of the most popular approaches in practical scheduling. Being developed for the makespan problem this method can also be generalized to the maximum lateness problem. For the unit execution time task system and parallel processors this generalization is known as the BruckerGareyJohnson algorithm. We characterize this algorithm by introducing an upper bound on the deviation of the criterion from its optimal value. The bound is stated in terms of parameters characterizing the problem, namely number of processors, the length of the longest path, and the total required processing time. We also derive a similar bound for the preemptive version of the Brucker-Garey-Johnson algorithm.

## Journal articles

Zinder, Y., Memar, J. & Singh, G. 2013, 'Discrete optimization with polynomially detectable boundaries and restricted level sets',

View/Download from: Publisher's site

*JOURNAL OF COMBINATORIAL OPTIMIZATION*, vol. 25, no. 2, pp. 308-325.View/Download from: Publisher's site

Walker, S.J. & Zinder, Y. 2013, 'The solvable cases of a scheduling algorithm',

View/Download from: Publisher's site

*Lecture Notes in Computer Science*, vol. 8283, no. 1, pp. 229-239.View/Download from: Publisher's site

When considering the NP-hard problem of scheduling precedence constrained tasks with preemptions on identical parallel machines with the goal of minimising the maximum lateness, approximation algorithms are commonly studied. It is desirable to characterise in some way the circumstances under which a given algorithm will provide an optimal solution. This paper considers a well-known scheduling algorithm called the Brucker-Garey-Johnson Algorithm, known to produce optimal schedules whenever the precedence constraints are in the form of in-trees. A new class of partial orders is presented and it is proved not only that the Brucker-Garey-Johnson Algorithm will solve every problem instance constrained by a partial order from that class but also that no larger class has this property.

Zinder, Y., Su, B., Singh, G. & Sorli, R. 2010, 'Scheduling UET-UCT tasks: branch-and-bound search in the priority space',

View/Download from: Publisher's site

*OPTIMIZATION AND ENGINEERING*, vol. 11, no. 4, pp. 627-646.View/Download from: Publisher's site

Hanen, C. & Zinder, Y. 2009, 'The worst-case analysis of the Garey-Johnson algorithm',

View/Download from: Publisher's site

*JOURNAL OF SCHEDULING*, vol. 12, no. 4, pp. 389-400.View/Download from: Publisher's site

Zinder, Y. & Singh, G. 2005, 'Preemptive scheduling on parallel processors with due dates',

View/Download from: Publisher's site

*Asia-Pacific Journal of Operational Research*, vol. 22, no. 4, pp. 445-462.View/Download from: Publisher's site

The paper presents a priority algorithm for the maximum lateness problem with parallel identical processors, precedence constraints, and preemptions. The presented algorithm calculates the priority of each task by constructing a schedule for the set of its successors. The algorithm is motivated by comparison of its nonpreemptive counterpart with other algorithms for the problem with unit execution time tasks. It is shown that the presented algorithm constructs an optimal schedule for the problem with two processors and arbitrary precedence constraints, and for the problem with an arbitrary number of processors and precedence constraints in the form of an in-tree. This proof also indicates that the presented algorithm allows the worst-case performance ratio previously established for the so-called Muntz-Coffman algorithm for a particular case of the considered problem where all due dates are zero. World Scientific Publishing Co. & Operational Research Society of Singapore.

Zinder, Y., Do, V. & Oguz, C. 2005, 'Computational complexity of some scheduling problems with multiprocessor tasks',

*Discrete Optimisation*, vol. 2, pp. 391-408. The paper is concerned with scheduling problems with multiprocessor tasks and presets conditions under which such problems can be solved inpolynomial time. The application of these conditions is illutrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem witha UET task system, two parallel processors, the criterion of total completion time, and precednece constraints in the form of out-trees

Oguz, C., Zinder, Y., Do, V., Janiak, A. & Lichtenstein, M. 2004, 'Hybrid flow-shop scheduling problems with multiprocessor task systems',

View/Download from: Publisher's site

*EUROPEAN JOURNAL OF OPERATIONAL RESEARCH*, vol. 152, no. 1, pp. 115-131.View/Download from: Publisher's site

Zinder, Y. 2003, 'An iterative algorithm for scheduling UET tasks with due dates and release times',

View/Download from: Publisher's site

*EUROPEAN JOURNAL OF OPERATIONAL RESEARCH*, vol. 149, no. 2, pp. 404-416.View/Download from: Publisher's site

Hung, A., Nguyen, H.T., Thornton, B.S. & Zinder, Y. 2003, 'Dynamic Programming Approach to Image Segmentation and its Application to Pre-processing of Mammograms',

*Australian Journal of Intelligent Information Processing Systems*, vol. 8, no. 2, pp. 51-56. Images egmentationis an importent componento f imagop rocessings irce significantt ime can be savedi f a region of interest is extracted by al efficient segmentationa lgorithm. A dynamic programming image segmentation algorithnr is presented. The algorithm is applicable to images with a large matrix of gray levels of pixel values and generatesa path separatingt he object from the background.T he report of a.na pplication of the proposed algorithm to digitised mammotramsc omplementsit s description.

Brucker, P., Knust, S., Roper, D. & Zinder, Y. 2000, 'Scheduling UET task systems with concurrency on two parallel identical processors',

*MATHEMATICAL METHODS OF OPERATIONS RESEARCH*, vol. 52, no. 3, pp. 369-387. Singh, G. & Zinder, Y. 2000, 'Worst-case performance of two critical path type algorithms',

*ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH*, vol. 17, no. 1, pp. 101-122. Brucker, P., Knust, S., Roper, D. & Zinder, Y. 2000, 'Scheduling UET task systems with concurrency on two parallel indentical processors',

View/Download from: Publisher's site

*Mathematical Methods of Operations Research*, vol. 52, no. 3, pp. 369-387.View/Download from: Publisher's site

Singh, G. & Zinder, Y. 2000, 'Worst-case performance of critical path type algorithms',

*International Transactions in Operational Research*, vol. 7, no. 4-5, pp. 383-399. Singh, G. & Zinder, Y. 2000, 'Worst-case performance of two critical path type algorithms',

*Asia Pacific Journal of Operational Research*, vol. 17, pp. 101-122. Zinder, Y. & Roper, D. 1998, 'An iterative algorithm for scheduling unit-time tasks with precedence constraints to minimise the maximum lateness',

View/Download from: Publisher's site

*ANNALS OF OPERATIONS RESEARCH*, vol. 81, pp. 321-340.View/Download from: Publisher's site

Zinder, Y. 1986, 'The efficient algorithm for deterministic scheduling problem with parallel machines',

*Cybernetics and Systems Analysis*, vol. 2. Zinder, Y. & Shkurba, V. 1985, 'Effective iterative algorithms in scheduling theory',

*Cybernetics and Systems Analysis*, vol. 1, pp. 86-90. Zinder, Y. 1982, 'Topological Sorting',

*Programming and Computer Software*, vol. 6. Zinder, Y. & Portougal, V. 1976, 'Mathematical model of operative control of the course of production',

*Cybernetics and Systems Analysis*, vol. 11, no. 2, pp. 264-270.**Selected Peer-Assessed Projects**