Associate Professor Yakov Zinder

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.
View/Download from: UTSePress
View description>>

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.

Chew, K., Langtry, T.N., Zinder, Y., Yu, Q. & Li, L. 2012, 'Estimation of biochemical parameters from leaf photosynthesis', ANZIAM Journal, vol. 53, pp. C218-C235.
View description>>

The objective of measuring leaf photosynthesis using infrared gas analysis is to determine key indicators of plant eco-physiology, including light and CO2 compensation and saturation points, and critical thresholds of temperature. These and other biochemical parameters in photosynthesis models define specific response curves of photosynthetic rate to environmental variables, such as light intensity, temperature, and CO2. Since these parameters cannot regularly be measured in the field, modellers normally adopt laboratory values as universal ones even though the values of these parameters may vary across plant species. This study investigates the identification of parameter values from data sets obtained from field measurement.

Zinder, Y., Su, B., Singh, G. & Sorli, R. 2011, 'Scheduling UET-UCT tasks: bransch-and-bound search in the priority space', Optimization and Engineering, vol. 11, no. 4, pp. 627-646.

Hanen, C. & Zinder, Y. 2009, 'The worst-case analysis of the Garey-Johnson algorithm', Journal Of Scheduling, vol. 12, no. 4, pp. 389-400.
View/Download from: UTSePress | Publisher's site
View description>>

The Garey-Johnson algorithm is a well known polynomial-time algorithm constructing an optimal schedule for the maximum lateness problem with unit execution time tasks, two parallel identical processors, precedence constraints and release times. The paper is concerned with the worst-case analysis of a generalization of the Garey-Johnson algorithm to the case of arbitrary number of processors. In contrast to other algorithms for the maximum lateness problem, the tight performance guarantee for the even number of processors differs from the tight performance guarantee for the odd number of processors.

Zinder, Y., Do, V. & Oguz, C. 2005, 'Computational complexity of some scheduling problems with multiprocessor tasks', Discrete Optimisation, vol. 2, pp. 391-408.
View/Download from: UTSePress | Publisher's site
View description>>

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

Zinder, Y. & Singh, G. 2005, 'Preemptive scheduling on parallel processors with due dates', Asia-Pacific Journal of Operational Research, vol. 22, no. 4, pp. 445-462.
View/Download from: UTSePress | Publisher's site
View description>>

The paper presents a priority algorithm for the maximum lateness problem with parallel identical processors, presedence 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 constaints, 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 performace ratio previously extablished for the so-called Muntz-Coffman algorithm for a particular case of the considered problem where all due dates are zero.

Oguz, C., Zinder, Y., Do, V., Janiak, A. & Lichtenstein, M. 2004, 'Hybrid flow-shop scheduling problems with multiprocessor task systems', European Journal of Operational Research, vol. 152, pp. 115-131.
View/Download from: UTSePress | Publisher's site
View description>>

Hybrid flow-shop problems and problems with multiprocessor task systems have remained subject of intensive research over several years. Hybrid flow-shop problems overcome one of the limitations of the classical flow-shop model by allowing parallel processors at each stage of task processing. Problems with multiprocessor task systems relax the limitation of the classical parallel processor model by permitting tasks that require more than one processor simultaneously. The great deal of interest for both types of problem, besides their obvious theoretical significance, was inspired by needs of various manufacturing and computing systems. In this paper we consider a model which amalgamates both above-mentioned generalizations. We show that, without precedence constraints and under the assumption that all processing times are bounded above, the makespan minimization problem is solvable in polynomial time, whereas the introduction of precedence constraints makes even the simplest version of this problem NP-hard. For the arbitrary processing time task systems, we present an approximation algorithm based on the idea of tabu search and discuss the results of computational experiments, which were performed to analyze the algorithm+s efficiency and sensitivity to variation in the input data.

Hung, W., 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.
View/Download from: UTSePress
View description>>

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.

Zinder, Y. 2003, 'An iterative algorithm for scheduling UET tasks with due dates and release times', European Journal Of Operational Research, vol. 149, no. 2, pp. 404-416.
View/Download from: UTSePress | Publisher's site

Brucker, P., Knust, S., Roper, D. & Zinder, Y. 2000, 'Scheduling UET task systems with concurrency on two parallel indentical processors', Mathematical Methods of Operations Research, vol. 52, no. 3, pp. 369-387.

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.
View description>>

Problems with unit execution time (UET) tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. Following Lloyd, we term such task systems systems with concurrency. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family.

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.

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', Annals Of Operations Research, vol. 81, pp. 321-343.

Zinder, Y. & Shkurba, V. 1985, 'Effective iterative algorithms in scheduling theory', Cybernetics and Systems Analysis, vol. 1, pp. 86-90.

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.

Zinder, Y., Nicorovici, N.A. & Langtry, T.N. 2011, 'Mathematica based platform for self-paced learning', Portsmouth, United Kingdom, July 2011 in Proceedings of the 10th International Conference on Technology in Mathematics Teaching (ICTMT10), ed Marie Joubert; Alison Clark-Wilson; Michael McCabe, University of Portsmouth, United Kingdom, pp. 203-208.

Zinder, Y., Memar, J. & Singh, G. 2010, 'Discrete optimisation with polynomially detectable boundaries and restricted level sets', international conference on Combinatorial optimization and applications, USA, December 2010 in Lecture Notes in computer Science Vol 6508: Combinatorial Optimization and Applications - 4th Annual International Conference on Combinatorial Optimization and Applications, ed Donghyun Kim, Kailua-Kona, Germany, pp. 142-156.
View/Download from: UTSePress | Publisher's site
View description>>

The paper describes an optimization procedure for a class of discrete optimization problems which is defined by certain properties of the boundary of the feasible region and level sets of the objective function. It is shown that these properties are possessed, for example, by various scheduling problems, including a number of well-known NP-hard problems which play an important role in scheduling theory. For an important particular case the presented optimization procedure is compared with a version of the branch-and-bound algorithm by means of computational experiments

Zinder, Y., Singh, G., Su, B. & Sorli, R.M. 2007, 'Scheduling UET-UCT tasks: branch-and-bound search in the priority space', International Conference on Optimization: Techniques And Applications, Kobe, Japan, December 2007 in 7th International conference on optimisation: techniques and applications (ICOTA7), ed Fukushima, M; Lau, MS; Nakayama, H; Nitta, N; Tanaka, M; Tatsumi, K; Wada, M; Wakatani, A; Watanabe, E; Yamashita, N; Yue W, Universal Academy Press Inc, Kobe, Japan, pp. 1-12.
View/Download from: UTSePress
View description>>

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', International Multiconference of Engineers and Computer Scientists, Kowloon, PEOPLES R CHINA, June 2006 in Imecs 2006: International Multiconference Of Engineers And Computer Scientists, ed Ao, SI; Lee, JA; Castillo, O; Chaudhuri, P; Feng, DD, International Association Engineers-Iaeng, Hong Kong, pp. 796-801.
View description>>

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 co

Zinder, Y. 2005, 'Scheduling UET tasks on parallel machines: strength of priority algorithms', National Conference of theAustralian Society for Operation Research, Perth, Australia, September 2005 in Proceedings of the 18th National Conference of the Australian Society for OPerations Research and the 11th Australian Optimisation Day, ed Cacetta, L; Rehbock, V., Western Australian Centre of Excellence in Industrial Optimisation, Curtin University of Technology, Perth, Australia, pp. 186-191.
View/Download from: UTSePress
View description>>

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.

Zinder, Y. & Singh, G. 2004, 'Preemptive scheduling on parallel processors with due dates', International Symposium on Scheduling, Japan, May 2004 in Proceedings of the International Symposium on Scheduling 2004, ed Kise, H., Japan Society of Mechanical Engineers, Tokyo, Japan, pp. 100-103.
View/Download from: UTSePress

Singh, G., Zinder, Y. 2000, 'Worst-case performance of critical path type algorithms', 15th National Conference of Australian Society for Operations Research, Gold Coast, January 1999 in 15th National Conference of Australian Society for Operations Research, ed E. Kozan, Australian Society for Operations Research, Australia, pp. 383-399.
View/Download from: UTSePress
View description>>

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 Brucker¦Garey¦Johnson 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.