#### Can supervise: YES

#### Publications

Ernst, A, Fung, J, Singh, G & Zinder, Y 2019, 'Flexible flow shop with dedicated buffers', *Discrete Applied Mathematics*, vol. 261, pp. 148-163.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2018 Elsevier B.V. A two-stage flexible flow shop is considered, where first- and second-stage machines form disjoint pairs, each with a buffer. The buffer capacity varies from pair to pair, and the buffer requirement varies from job to job. Each job is to be assigned to a pair of machines for processing and uses the required amount of buffer from the start till the end of its processing. Operations have equal duration. It is shown that, unless P=NP, no polynomial-time algorithm guarantees a makespan less than 4∕3 of the optimal. The paper presents two integer linear programs, compared by means of computational experiments. Both approaches utilise as a subroutine the developed polynomial-time algorithm for the case of equal buffers.

Czibula, OG, Gu, H & Zinder, Y 2018, 'Lagrangian relaxation versus genetic algorithm based metaheuristic for a large partitioning problem', *Theoretical Computer Science*, vol. 718, pp. 24-36.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2017 Elsevier B.V. This paper is concerned with a partitioning problem. One of the applications, and the motivation for this research, is the problem of class formation for training and retraining sessions at large electricity distributors. Two different approaches are developed. One is based on the Quadratic Multiple Knapsack formulation and Lagrangian relaxation. The other is a matheuristic developed as an amalgamation of Genetic Algorithms and Integer Programming. The approaches are tested by means of computational experiments. Both heuristics outperformed the direct application of quadratic programming, with the Lagrangian relaxation based approach performing the best on average, and the Genetic Algorithm based approach performing the best on the larger test cases.

Czibula, OG, Gu, H & Zinder, Y 2018, 'Planning personnel retraining: column generation heuristics', *JOURNAL OF COMBINATORIAL OPTIMIZATION*, vol. 36, no. 3, pp. 896-915.View/Download from: Publisher's site

Gu, H, Kononov, A, Memar, J & Zinder, Y 2018, 'Efficient Lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements', *Journal of Discrete Algorithms*, vol. 52-53, pp. 143-155.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2018 Elsevier B.V. The paper is concerned with minimisation of the total weighted completion time for the two-stage flow shop with a buffer. In contrast to the vast literature on this topic, the buffer requirement varies from job to job and a job occupies the buffer continuously from the start of its first operation till the completion of its second operation rather than only between operations. Such problems arise in supply chains requiring unloading and loading of minerals and in some multimedia systems. The problem is NP-hard in the strong sense, and we prove that if the order of jobs is fixed for one of the stages, then even for the criteria of the maximum completion time or the total completion time the problem remains NP-hard in the strong sense. Straightforward integer programming approach is impossible even for modest problem sizes. The paper presents a Lagrangian relaxation based decomposition approach that allows to use for each problem, obtained by this decomposition, a very fast algorithm. Several Lagrangian heuristics are evaluated by means of computational experiments.

Zinder, Y, Lazarev, AA, Musatova, EG & Tarasov, IA 2018, 'Scheduling the Two-Way Traffic on a Single-Track Railway with a Siding', *Automation and Remote Control*, vol. 79, no. 3, pp. 506-523.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2018, Pleiades Publishing, Ltd. The paper is concerned with scheduling the two-way traffic between two stations connected by a single-track railway with a siding. It is shown that if, for each station, the order in which trains leave this station is known or can be found, then for various objective functions an optimal schedule can be constructed in polynomial time using the method of dynamic programming. Based on this result, the paper also presents a polynomial-time algorithm minimising the weighted number of late trains.

Czibula, O, Gu, H, Russell, A & Zinder, Y 2017, 'A multi-stage IP-based heuristic for class timetabling and trainer rostering', *Annals of Operations Research*, vol. 252, no. 2, pp. 305-333.View/Download from: UTS OPUS or Publisher's site

#### View description

© 2015 Springer Science+Business Media New York We consider a timetabling and rostering problem involving periodic retraining of large numbers of employees at an Australian electricity distributor. This problem is different from traditional high school and university timetabling problems studied in the literature in several aspects. We propose a three-stage heuristic consisting of timetable generation, timetable improvement, and trainer rostering. Large-scale integer linear programming models for both the timetabling and the rostering components are proposed, and several unique operational constraints are discussed. We show that this solution approach is able to produce good solutions in practically acceptable time.

Czibula, OG, Gu, H, Hwang, FJ, Kovalyov, MY & Zinder, Y 2016, 'Bi-criteria sequencing of courses and formation of classes for a bottleneck classroom', *Computers and Operations Research*, vol. 65, pp. 53-63.View/Download from: UTS OPUS or Publisher's site

#### View description

In this paper, the problem of class formation and sequencing for multiple courses subject to a bottleneck

classroom with an ordered bi-criteria objective is studied. The problem can be modelled as a singlemachine

batch scheduling problem with incompatible job families and parallel job processing in batches,

where the batch size is family-dependent. For the minimisation of the number of tardy jobs, the strong

NP-hardness is proven. For the performance measure of the maximum cost, we consider single criterion

and bi-criteria cases. We present an Oðn2log nÞ algorithm, n is the number of jobs, for both cases. An

Integer Programming model as well as Simulated Annealing and Genetic Algorithm matheuristics to

solve a fairly general case of the bi-criteria problem is presented and computationally tested.

Fung, J & Zinder, Y 2016, 'Permutation schedules for a two-machine flow shop with storage', *OPERATIONS RESEARCH LETTERS*, vol. 44, no. 2, pp. 153-157.View/Download from: UTS OPUS or Publisher's site

Fung, J, Singh, G & Zinder, Y 2015, 'Capacity planning in supply chains of mineral resources', *INFORMATION SCIENCES*, vol. 316, pp. 397-418.View/Download from: UTS OPUS or Publisher's site

#### View description

The paper addresses the existing gap in the literature on the optimisation in capacity planning for mineral supply chains. The presented optimisation procedure aims at minimising the cost of infrastructure expansion for any given scenario of future demand. The optimisation procedure is designed as a matheuristic - a hybridisation of mixed integer linear programming (MILP), and a simulated annealing based scheduler. The optimisation procedure is iterative in nature and has the following distinctive features. Each iteration starts with generating a MILP model and finding a minimal cost infrastructure expansion for this model. Then, the scheduler analyses the MILP solution by constructing a schedule. In constructing this schedule, the scheduler reduces its search space using the MILP solution. The scheduler identifies bottlenecks in the infrastructure, which are used for generating a new MILP model at the next iteration. The MILP and the scheduler use different levels of data aggregation and their interaction mechanism is designed as a solution process of a bi-criteria optimisation problem. The computational experiments on data, originating from the world's largest coal exporter, shows the ability of the developed matheuristic to solve industrial-scaled instances of the problem.

Zinder, Y & Walker, S 2015, 'Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness', *DISCRETE APPLIED MATHEMATICS*, vol. 196, pp. 28-53.View/Download from: Publisher's site

Zinder, Y, Memar, J & Singh, G 2013, 'Discrete Optimization With Polynomially Detectable Boundaries And Restricted Level Sets', *Combinatorial Optimization and Applications*, vol. 25, no. 2, pp. 308-325.View/Download from: UTS OPUS or 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 one of these problems the presented optimization procedure is compared with a version of the branch-and-bound algorithm by means of computational experiments

Langtry, TN, Chew, KL, Zinder, Y, Yu, Q & Li, L 2012, 'Estimation of biochemical parameters from leaf photosynthesis', *ANZIAM Journal*, vol. 53, no. EMAC2011, pp. C218-C235.View/Download from: UTS OPUS or Publisher's site

#### 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 2010, 'Scheduling UET-UCT tasks: bransch-and-bound search in the priority space', *Optimization and Engineering*, vol. 11, no. 4, pp. 627-646.View/Download from: UTS OPUS or Publisher's site

#### View description

The paper is concerned with 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 theory and was originally inspired by the applications to multi-processor computer systems. It is well known that for both criteria the problem is NP-hard in the strong sense. The paper presents an implementation of the branch-and-bound method which does not partition the feasible region explicitly. The theoretical results are complemented by computational experiments.

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: UTS OPUS or 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 & 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: UTS OPUS or 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.

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: UTS OPUS

#### 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

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: UTS OPUS or 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 algorithms efficiency and sensitivity to variation in the input data.

Hung, A, Nguyen, HT, Thornton, BS & 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: UTS OPUS

#### 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: UTS OPUS or Publisher's site

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/Download from: Publisher's site

#### 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.

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

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.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, YA 1982, 'ALPHA-TOPOLOGICAL SORTING.', *Programming and Computer Software (English Translation of Programmirovanie)*, vol. 8, no. 6, pp. 346-348.

#### View description

The complexity of alpha-topological sorting is investigated. An effective algorithm of alpha-topological sorting is proposed and its application domain is described.

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 & 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: UTS OPUS

#### 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.

Berlińska, J, Kononov, A & Zinder, Y 2020, 'Two-Machine Flow Shop with a Dynamic Storage Space and UET Operations', *Advances in Intelligent Systems and Computing*, pp. 1139-1148.View/Download from: Publisher's site

#### View description

© 2020, Springer Nature Switzerland AG. The paper establishes the NP-hardness in the strong sense of a two-machine flow shop scheduling problem with unit execution time (UET) operations, dynamic storage availability, job dependent storage requirements, and the objective to minimise the time required for the completion of all jobs, i.e. to minimise the makespan. Each job seizes the required storage space for the entire period from the start of its processing on the first machine till the completion of its processing on the second machine. The considered scheduling problem has several applications, including star data gathering networks and certain supply chains and manufacturing systems. The NP-hardness result is complemented by a polynomial-time approximation scheme (PTAS) and several heuristics. The presented heuristics are compared by means of computational experiments.

Gu, H, Joyce, M, Lam, HC, Woods, M & Zinder, Y 2019, 'A Genetic Algorithm for Assigning Train Arrival Dates at a Maintenance Centre', *IFAC-PapersOnLine*, IFAC Conference on Manufacturing Modelling, Management and Control, IFAC Secretariat, Berlin, Germany, pp. 957-962.View/Download from: UTS OPUS or Publisher's site

#### View description

The paper is concerned with planning heavy maintenance of train-sets at a maintenance centre. The heavy maintenance process is complex and, for each train-set, the actual duration of maintenance is uncertain at the time of planning. The allocation of the dates when train-sets should arrive at the maintenance centre is crucial phase of the planning procedure. The objective function is a weighted sum of two components, the expected total penalty for not meeting the required number of train-sets in active service and the total cost for the deviation (earliness and tardiness) from the desired dates of arrival. A genetic algorithm is presented for the considered problem and its effectiveness is demonstrated by the computational experiments that used real-world data provided by a big maintenance centre.

Gu, H, Memar, J & Zinder, Y 2019, 'Improved Lagrangian relaxation based optimization procedure for scheduling with storage', *IFAC PAPERSONLINE*, 9th IFAC/IFIP/IFORS/IISE/INFORMS Conference on Manufacturing Modelling, Management and Control (IFAC MIM), ELSEVIER, Berlin, GERMANY, pp. 100-105.View/Download from: UTS OPUS or Publisher's site

Gu, H, Zhang, Y & Zinder, Y 2019, 'Lagrangian Relaxation in Iterated Local Search for the Workforce Scheduling and Routing Problem', *Analysis of Experimental Algorithms. SEA 2019. Lecture Notes in Computer Science*, Special Event on Analysis of Experimental Algorithms, Springer, Kalamata, Greece.View/Download from: UTS OPUS or Publisher's site

#### View description

The efficiency of local search algorithms for vehicle routing problems often increases if certain constraints can be violated during the search. The penalty for such violation is included as part of the objective function. Each constraint, which can be violated, has the associated parameters that specify the corresponding penalty. The values of these parameters and the method of their modification are usually a result of computational experiments with no guarantee that the obtained values and methods are equally suitable for other instances. In order to make the optimisation procedure more robust, the paper suggests to view the penalties as Lagrange multipliers and modify them as they are modified in Lagrangian relaxation. It is shown that such modification of the Xie-Potts-Bektaş Algorithm for the Workforce Scheduling and Routing Problem permits to achieve without extra tuning the performance comparable with that of the original Xie-Potts-Bektaş Algorithm.

Kononov, A, Memar, J & Zinder, Y 2019, 'Flow shop with job–dependent buffer requirements—a polynomial–time algorithm and efficient heuristics', *Mathematical Optimization Theory and Operations Research (LNCS)*, International Conference on Mathematical Optimization Theory and Operations Research, Springer, Ekaterinburg, Russia, pp. 342-357.View/Download from: UTS OPUS or Publisher's site

#### View description

© Springer Nature Switzerland AG 2019. The paper is concerned with the two-machine flow shop, where each job needs storage space (a buffer requirement) during the entire time of its processing. The buffer requirement is determined by the duration of job’s first operation. The goal is to minimise the time needed for the completion of all jobs. This scheduling problem is NP-hard in the strong sense even for very restricted cases such as the case with a given order of jobs processing on one of the machines. The paper contributes to the efforts of establishing the borderline between the NP-hard and polynomial-time solvable cases by proving that there exists a polynomial-time algorithm which constructs an optimal schedule if the duration of each operation does not exceed one-fifth of the buffer capacity. The presented polynomial-time algorithm is used as a basis for a heuristic for the general case. This heuristic is complemented by a Lagrangian relaxation based heuristic and a bin-packing based constructive heuristic. The heuristics are tested by computational experiments.

Gu, H, Memar, J & Zinder, Y 2018, 'Efficient lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements', *Combinatorial Algorithms (LNCS)*, International Workshop on Combinatorial Algorithms, Springer, Singapore, Singapore, pp. 312-324.View/Download from: UTS OPUS or Publisher's site

#### View description

© Springer International Publishing AG, part of Springer Nature 2018. The paper is concerned with minimisation of total weighted completion time for the two-stage flow shop with a buffer. In contrast to the vast literature on this topic, the buffer requirement varies from job to job and a job occupies the buffer continuously from the start of its first operation till the completion of its second operation rather than only between operations. Such problems arise in supply chains requiring unloading and loading of minerals and in some multimedia systems. The problem is NP-hard and the straightforward integer programming approach is impossible even for modest problem sizes. The paper presents a Lagrangian relaxation based decomposition approach that allows to use for each problem, obtained by this decomposition, a very fast algorithm. Several Lagrangian heuristics are evaluated by means of computational experiments.

Gu, H, Memar, J & Zinder, Y 2018, 'Scheduling batch processing in flexible flowshop with job dependent buffer requirements: Lagrangian relaxation approach', *WALCOM 2018: WALCOM: Algorithms and Computation LNCS)*, International Workshop on Algorithms and Computation, Springer, Dhaka, Bangladesh, pp. 119-131.View/Download from: UTS OPUS or Publisher's site

#### View description

© Springer International Publishing AG, part of Springer Nature 2018. The paper presents a Lagrangian relaxation based algorithm for scheduling jobs in the two-stage flowshop where the first stage is comprised of several parallel identical machines and the second stage consists of a single machine processing jobs in the predefined batches. Motivated by applications where unloading and loading occur when the means of transportation are changed, the processing of the jobs, constituting a batch, can commence only if this batch has been allocated a portion of a limited buffer associated with the flowshop. This portion varies from batch to batch and is released only after the completion of the batch processing on the second stage machine. Each batch has a due date and the objective is to minimise the total weighted tardiness. The effectiveness of the proposed algorithm is demonstrated by computational experiments.

Gu, H, Memar, J & Zinder, Y 2016, 'Search Strategies for Problems with Detectable Boundaries and Restricted Level Sets', *Data and Decision Sciences in Action*, Australian-Society-for-Operations-Research Conference, Springer, Sydney, Australia, pp. 149-162.View/Download from: UTS OPUS or Publisher's site

#### View description

The chapter is concerned with a class of discrete optimisation problems which includes a number of classical NP-hard scheduling problems. The considered solution method is an iterative procedure that at each iteration, it computes a lower bound on the optimal objective value and searches for a feasible solution attaining this bound. The chapter describes three search methods—descending search, ascending search, and their combination. These methods are illustrated by considering their implementations for the unit execution time unit communication delay maximum lateness problem with parallel identical machines. The resultant algorithms are compared by means of computational experiments.

Memar, J, Zinder, Y & Kononov, AV 2018, 'Worst-case analysis of a modification of the brucker-garey-johnson algorithm', *OPTA 2018: Optimization Problems and Their Applications*, International Conference on Optimization Problems and Their Applications, Springer, Omsk, Russia, pp. 78-92.View/Download from: Publisher's site

#### View description

© Springer International Publishing AG, part of Springer Nature 2018. The paper presents the worst-case analysis of a polynomial-time approximation algorithm for the maximum lateness scheduling problem with parallel identical machines, arbitrary processing times and arbitrary precedence constraints. The algorithm is a modification of the Brucker-Garey-Johnson algorithm originally developed as an exact algorithm for the case of the problem with unit execution time tasks and precedence constraints represented by an in-tree. For the case when the largest processing time does not exceed the number of machines, we obtain a worst-case performance guarantee which is tight for arbitrary large instances of the considered maximum lateness problem. It is shown that, if the largest processing time is greater than the number of machines, then the worst-case performance guarantee for the list algorithm, obtained by Hall and Shmoys, is tight.

Czibula, O, Gu, H & Zinder, Y 2016, 'A Lagrangian Relaxation-Based Heuristic to Solve Large Extended Graph Partitioning Problems', *Lecture Notes in Computer Science*, International Workshop on Algorithms and Computation (WALCOM), Springer International Publishing, Kathmandu, Nepal, pp. 327-338.View/Download from: UTS OPUS or Publisher's site

#### View description

The paper is concerned with the planning of training sessions in large organisations requiring periodic retraining of their staff. The allocation of students must take into account student preferences as well as the desired composition of study groups. The paper presents a bicriteria Quadratic Multiple Knapsack formulation of the considered practical problem, and a novel solution procedure based on Lagrangian relaxation. The paper presents the results of computational experiments aimed at testing the optimisation procedure on real world data originating from Australia’s largest electricity distributor. Results are compared and validated against a Genetic Algorithm based matheuristic

Czibula, O, Gu, H & Zinder, Y 2016, 'Timetabling of Workplace Training: A Combination of Mathematical Programming and Simulated Annealing', *PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling*, International Conference of the Practice and Theory of Automated Timetabling, PATAT, Udine, Italy, pp. 95-107.View/Download from: UTS OPUS

#### View description

The paper is concerned with the problem of scheduling workplace

training, which arises in a broad range of organisations, from the hospital

placements of nursing students to apprentice training at organisations such as electricity distributors. The problem can be viewed as a generalisation of the open shop scheduling problem. The paper discusses the complexity of the considered problem, and presents an optimisation procedure, which is a sequential application of integer linear programming and simulated annealing. The effectiveness of the proposed optimisation procedure was demonstrated by computational experiments using data with typical characteristics of a real world problems arising at large electricity distributors. The computational

experiments show that the proposed optimisation procedure produces superior solutions on average compared to those from a general purpose MIP solver.

Czibula, OG, Gu, H & Zinder, Y 2016, 'Scheduling Personnel Retraining:Column Generation Heuristics', *Scheduling Personnel Retraining: Column Generation Heuristics (LNCS)*, International Symposium on Combinatorial Optimization, Springer, Vietri sul Mare, Italy, pp. 213-224.View/Download from: UTS OPUS or Publisher's site

#### View description

Many organisations need periodic retraining of staff. Due to certain requirements on the composition of study groups, the planning of training sessions is an NP-hard problem. The paper presents linear and nonlinear mathematical programming formulations of this problem together with three column generation based heuristic optimisation procedures. The procedures are compared by means of computational experiments that use data originating from a large Australian electricity distributor with several thousand employees.

Fung, J, Zinder, Y & Singh, G 2016, 'Flexible Flow Shop with Storage: Complexity and Optimisation Methods', *IFAC Proceedings Volumes (IFAC-PapersOnline)*, IFAC Conference on Manufacturing Modelling, Management and Control, Elsevier, Troyes, France, pp. 237-242.View/Download from: UTS OPUS or Publisher's site

#### View description

The paper is concerned with a two-stage flexible flow shop with a buffer under the assumption that all operations have the same processing time and that each job can be processed on a machine only if a certain amount of buffer space is allocated to this job. The amount of buffer space to be allocated differs from job to job. The buffer is shared by all machines and has limited size. The objective function is the makespan. The application area includes supply chains which involve loading and unloading operations, and problems arising in computer systems with shared memory. It is proven that in general, the problem is NP-hard in the strong sense, but in the case of two-machines, it is solvable in polynomial-time. For the general case, several integer linear programming models are presented and compared by means of computational experiments. The presented integer linear programming models implement various ideas such as symmetry breaking constraints, knapsack type cutting planes and the results of the analysis of the structure of optimal schedules.

Zinder, Y, Lazarev, A, Musatova, E, Tarasov, I & Khusnullin, N 2016, 'Two-Station Single Track Scheduling Problem', *IFAC papers online*, IFAC Conference on Manufacturing Modelling, Management and Control, Elsevier, Troyes, France, pp. 231-236.View/Download from: UTS OPUS or Publisher's site

#### View description

Single track segments are common in various railway networks, in particular in various supply chains. For such a segment, connecting two stations, the trains form two groups, depending on what station is the initial station for the journey between these two stations. Within a group the trains differ by their cost functions. It is assumed that the single track is sufficiently long so several trains can travel in the same direction simultaneously. The paper presents polynomial-time algorithms for different versions of this two-station train scheduling problem with a single railway track. The considered models differ from each other by their objective functions.

Czibula, OG, GU, H, Hwang, FJ, Kovalyov, MY & Zinder, Y 2015, 'Class formation and multiple courses sequencing', ASOR Recent Advances in Operations Research,.

Czibula, O, Gu, H, Russell, A & Zinder, Y 2014, 'A Multi-Stage IP-Based Heuristic for Class Timetabling and Trainer Rostering', *Proceedings of the 10th International Conference of the Practice and Theory of Automated Timetabling*, Practice and Theory of Automated Timetabling, Springer, York, United Kingdom, pp. 102-127.View/Download from: UTS OPUS

Memar, J, Singh, G & Zinder, Y 2013, 'Scheduling partially ordered UET tasks on dedicated machines', *IFAC Proceedings Volumes (IFAC-PapersOnline)*, IFAC Conference on Manufacturing Modelling, Management, and Control, Elsevier, Saint Petersburg, Russia, pp. 1672-1677.View/Download from: UTS OPUS or Publisher's site

#### View description

The paper is concerned with scheduling partially ordered unit execution time tasks on dedicated machines. The considered scheduling model is important in control of different systems, in particular computer systems. The presented algorithm is an alternative to the conventional branch-and-bound method. In contrast to the branch-and-bound method with its single search tree, corresponding to partitioning of the feasible region, the presented method involves a sequence of search trees each associated with a certain portion of the domain of the objective function. The branching is based on a generalisation of the Garey-Johnson due date modification. The performance of the presented algorithm is compared by means of computational experiments with a version of the branch-and-bound algorithm. © IFAC.

Walker, SJ & Zinder, Y 2013, 'The solvable cases of a scheduling algorithm', *Lecture Notes in Computer Science*, International Symposium on Algorithms and Computation, Springer, Hong Kong, PEOPLES R CHINA, pp. 229-239.View/Download from: UTS OPUS or Publisher's site

#### View description

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, Nicorovici, NA & Langtry, T 2011, 'Mathematica based platform for self-paced learning', *International Conference on Technology in Mathematics Teaching (ICTMT10)*, International Conference on Technology in Mathematics Teaching, University of Portsmouth, Portsmouth, United Kingdom, pp. 203-208.View/Download from: UTS OPUS

#### View description

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.

Zinder, Y, Memar, J & Singh, G 2010, 'Discrete optimisation with polynomially detectable boundaries and restricted level sets', *Lecture Notes in computer Science Vol 6508: Combinatorial Optimization and Applications - 4th Annual International Conference on Combinatorial Optimization and Applications*, international conference on Combinatorial optimization and applications, Kailua-Kona, USA, pp. 142-156.View/Download from: UTS OPUS or 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, Nicorovici, NA & Langtry, T 2011, 'Mathematica based platform for self-paced learning', *Proceedings of EDULEARN 10*, EDULEARN, International Association of Technology, Education and Development, Spain, pp. 323-330.

#### View description

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 2012, 'Capacity planning for a coal supply chain', *The 2nd International Conference on Logistics and Transport*, Lincoln University, New Zealand.

Zinder, Y & Walker, SJ 2009, 'Scheduling flexible multiprocessor tasks on parallel machines', *9th Workshop on Models and Algorithms for Planning and Scheduling Problems*, Workshop on Models and Algorithms for Planning and Scheduling Problems, Abbey Rolduc, Netherlands, pp. 23-25.

#### View description

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, RM 2007, 'Scheduling UET-UCT tasks: branch-and-bound search in the priority space', *7th International conference on optimisation: techniques and applications (ICOTA7)*, International Conference on Optimization: Techniques And Applications, Universal Academy Press Inc, Kobe, Japan, pp. 1-12.View/Download from: UTS OPUS

#### 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', *Imecs 2006: International Multiconference Of Engineers And Computer Scientists*, International Multiconference of Engineers and Computer Scientists, International Association Engineers-Iaeng, Kowloon, PEOPLES R CHINA, 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

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*, 2nd Multidisciplinary International Conference on Schduling: theory and applications, New York University, New York, pp. 445-452.

#### View description

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.

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*, 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications, Stern School of Business, New York University, New York, pp. 453-470.

#### View description

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.

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*, National Conference of theAustralian Society for Operation Research, Western Australian Centre of Excellence in Industrial Optimisation, Curtin University of Technology, Perth, Australia, pp. 186-191.View/Download from: UTS OPUS

#### 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', *Proceedings of the International Symposium on Scheduling 2004*, International Symposium on Scheduling, Japan Society of Mechanical Engineers, Japan, pp. 100-103.View/Download from: UTS OPUS

Hanen, C & Zinder, Y 2002, 'The worst-case analysis of the Garey-Johnson algorithm', *8th International Workshop on Project Management and Scheduling*, 8th International Workshop on Project Management and Scheduling, The European Journal of Operational Research, Valencia, Spain.

#### View description

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 1999, 'Worst-case performance of critical path type algorithms', *15th National Conference of Australian Society for Operations Research*, 15th National Conference of Australian Society for Operations Research, Australian Society for Operations Research, Gold Coast, pp. 383-399.View/Download from: UTS OPUS

#### 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.

#### Projects

**Selected projects**