Hanyu received his Bachelor in industrial automation (1994), Master in control theory and application (1997), and Ph.D in power engineering and automation (1999), all from the Shanghai Jiao Tong University, China.
Since 2001 he has held positions as Lecturer and Associate Professor at the Shanghai Jiao Tong University until 2007 when he immigrated to Australia. He joined UTS in February 2013 as a lecturer in operations research.
Hanyu has extensive experiences in different industries. From 1999 to 2001 he worked as a senior wireless communication engineer at ZTE, one of the largest telecommunication company in China. From 2007 to 2011 he worked as a researcher for CTI, Melbourne, Australia, focusing on the optimisation engines for various airline management problems. From 2011 to 2013 he worked as a researcher for National ICT Australia (NICTA) in the optimisation group.
- Member of program committee of ASOR16 (24th National Conference of the Australian Society for Operations Research)
- Member of the Association for Constraint Programming
- Member of the Optimisation Group of UTS Transportation Research Centre
Can supervise: YES
Hanyu has wide research interests in the field of combinatorial optimisation. He has particular interests including:
- decomposition methods and their applications to large scale real world problems including project scheduling, airline scheduling and rostering, transportation, production planning and scheduling;
- cutting planes for integer programming;
- meta-heuristics and matheuristics
- hybridisation of mathematical programming and constraint programming
- non-smooth optimisation
LP0883855 Methods and software for efficiently solving the transportation crewing problem [2008 - 2012]
Researchers Prof MG Wallace; Prof GI Webb; A/Prof NL Boland; Mr IR Evans; Dr H Gu
Funding Amount $840,000
Funding Scheme ARC Linkage Projects
Brief description This project will target major savings in airlines, trucking, rail and public transport, with resulting benefits for industrial logistics, travel and tourism. The results discovered within the project will enable the industrial partner, CTI, to develop solutions for major companies worldwide. The results can also be transferred to other industrial optimisation applications, such as mining, services and manufacturing. Finally the project will build on Australia's international prominence in data analysis and combinatorial optimisation, and capitalise on a major opportunity for the Australian software industry.
Hanyu teaches and coordinates the following subjects:
- 37141 (35141) Introduction to quantitative management
- 33230 (Summer) Mathematical modelling 2
- 37345 Quantitative Management Practice
Hanyu also contributes to the teaching of the following subjects:
- 37171 Programming for informatics
- 37233 Linear algebra
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: Publisher's site
© 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: Publisher's site
© 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.
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: Publisher's site
© 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: Publisher's site
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.
Thiruvady, D, Wallace, M, Gu, H & Schutt, A 2014, 'A lagrangian relaxation and ACO hybrid for resource constrained project scheduling with discounted cash flows', JOURNAL OF HEURISTICS, vol. 20, no. 6, pp. 643-676.View/Download from: Publisher's site
Gu, H 2008, 'Computation of approximate alpha-points for large scale single machine scheduling problem', Computers & Operations Research, vol. 35, no. 10, pp. 3262-3275.View/Download from: Publisher's site
This paper studies the linear programming (LP) relaxation of xjt-formulation of the single machine scheduling problem 1|rj|?wjCj. The Lagrangian relaxation approach is proposed to cope with the computational difficulties for large problems. Since it can still be time consuming if highly accurate LP relaxation is required, the effect of approximate solution is studied with respect to the a-point heuristic. A two-stage proximal bundle algorithm is designed for the computation of the approximate solution. Results of numerical experiments show the efficiency of the proposed algorithm for large problems
He, B, Luo, L, Hu, J & Gu, HY 2008, 'Smoothing algorithm for high speed machining at corner', Shanghai Jiaotong Daxue Xuebao/Journal of Shanghai Jiaotong University, vol. 42, no. 1, pp. 83-86.
Making feed speed smooth along the corner of two adjoining moves is the key measure to protect the machine tools and assure the machining quality and the efficiency of high speed machinery process. This paper presented an algorithm to make smooth the track and the velocity by adding adjoining moves vectors based on trapezoidal velocity profile. The algorithm is proposed for interpolating adjoining moves simultaneously according to the maximum distance decelerating to zero. This algorithm is verified to get good machining quality and velocity at the corner when high speed machining.
Liu, L, Gu, H & Xi, Y 2008, 'Rescheduling Algorithm Based on Rolling Horizon Decomposition for a Dynamic Job Shop with Uncertain Arriving Time', Chinese Journal of Mechanical Engineering, vol. 44, no. 5, pp. 68-75.
The dynamic job shop scheduling with uncertain arriving time is studied,and the objective is to minimize total tardiness of all jobs.When rescheduling is frequent,the computational efficiency of the scheduling algorithm is necessarily high.Based on the rolling horizon decomposition,the critical operation set is denoted.A hybrid genetic algorithm is proposed to determine the critical operation set as well as optimizing total tardiness.The hybrid scheduler is used to convert the chromosome into partially feasible schedule,and the improved modified operation rule is used to determine the sequence of the remaining operations out of the chromosome.Then the fitness is evaluated by the objective value of the complete scheduling for the total operations to process.The simulation results of many instances show that the proposed algorithm significantly improves the computational efficiency compared with the genetic algorithm based on the complete operation set,and the performance of scheduling is satisfying
Xia, L & Gu, HY 2008, 'SOM-based approach for addressing multi-criteria scheduling problems', Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, vol. 14, no. 4.
To solve the posterior multi-criteria scheduling problems, a new method based on Self-Organization feature Map neural network (SOM) was presented to generate approximate Pareto boundaries. Firstly, Lagrange relaxation algorithm was applied to obtain several Pareto optima which were exploited to divide the search space into several domains. For each domain, two simultaneously running SOM were constructed to explore the remaining Pareto optima. According to the characteristics of multi-criteria scheduling, a new definition of neighbor for neural network training was proposed. Numerical experiments demonstrated the feasibility and the effectiveness of this algorithm.
Zhang, W-G & Wang, Y-L 2008, 'An analytic derivation of admissible efficient frontier with borrowing', European Journal of Operational Research, vol. 184, no. 1, pp. 229-243.View/Download from: Publisher's site
Zuo, Y, Gu, H & Xi, Y 2008, 'Study on constraint scheduling algorithm for job shop problems with multiple constraint machines', International Journal Of Production Research, vol. 46, no. 17, pp. 4785-4801.View/Download from: Publisher's site
This paper focuses on a job-shop scheduling problem with multiple constraint machines (JSPMC). A constraint scheduling method for the JSPMC is proposed. It divides the machines in the shop into constraint and non-constraint machines based on a new identification method, and formulates a reduced problem only for constraint machines while replacing the operations of non-constraint machines with time lags. The constraint machines are scheduled explicitly by solving the reduced problem with an efficient heuristic, while the non-constraint machines are scheduled by the earliest operation due date (EODD) dispatching rule. Extensive computational results indicate that the proposed constraint scheduling algorithm can obtain a better trade-off between solution quality and computation time compared with various versions of the shifting bottleneck (SB) methods for the JSPMC.
Liu, L, Gu, H & Xi, Y 2007, 'Robust and stable scheduling of a single machine with random machine breakdowns', International Journal Of Advanced Manufacturing Technology, vol. 31, no. 7, pp. 645-654.View/Download from: Publisher's site
Liu, L, Gu, HY & Xi, YG 2007, 'Robust scheduling in a Just-in-time single machine system with processing time uncertainty', Kongzhi yu Juece/Control and Decision, vol. 22, no. 10.
A two-loop co-evolutionary genetic algorithm is proposed to solve the absolute robust scheduling for a Just-in-time single machine with significant processing time uncertainty. The worst-case performance of a predictive schedule over the range of job processing times is optimized. The outer loop of the proposed algorithm is to determine the job sequence on machine and the inner loop searches for the processing time scenario with worst-case performance for a given sequence. The simulation results show the proposed method is very effective compared with the deterministic scheduling method based on expected job processing times.
Wang, XF & Gu, HY 2007, 'Improved scheduling strategy for batching tools in semiconductor wafer fabrication', Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, vol. 13, no. 6, pp. 1115-1120.
The scheduling problem for parallel batching tools with incompatible families in semiconductor wafer fabrication was studied. To improve the performance of on-time delivery in semiconductor manufacturing, aimed to minimize the Total Weighted Tardiness (TWT), an improved Apparent Tardiness Cost (ATC)-Batch Apparent Tardiness Cost (BATC) scheduling rule was proposed, which controlled SUBsection of Work in Process (SUBWIP). Result of simulation showed that TWT was effectively reduced by proposed method.
Yan, Z, Hanyu, G & Yugeng, X 2007, 'Modified bottleneck-based heuristic for large-scale job-shop scheduling problems with a single bottleneck', Journal of Systems Engineering and Electronics, vol. 18, no. 3, pp. 556-565.
Yan, Z, Hanyu, G & Yugeng, X 2007, 'Modified bottleneck-based heuristic for large-scale job-shop scheduling problems with a single bottleneck * * This project was supported by the National Natural Science Foundation of China (60274013; 60474002) and Shanghai Development Found for Science and Technology (04DZ11008).', Journal of Systems Engineering and Electronics, vol. 18, no. 3, pp. 556-565.View/Download from: Publisher's site
A modified bottleneck-based (MB) heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck (SB) procedure. In this algorithm, the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules. Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems. Furthermore, it can obtain a good solution in a short time for large-scale jobshop scheduling problems. © 2007 The Second Academy of China Aerospace Science & Industry Cooperation.
Zhang, H, Gu, H & Xi, Y 2007, 'A Benders decomposition algorithm for base station planning problem in WCDMA networks', Computers & Operations Research, vol. 38, no. 11, pp. 1674-1687.
Zhang, H, Xi, Y & Gu, H 2007, 'A rolling window optimization method for large-scale WCDMA base stations planning problem', European Journal Of Operational Research, vol. 183, no. 1, pp. 370-383.View/Download from: Publisher's site
The large scale optimization problem of WCDMA wireless networks base station planning is studied by means of the basic principle of rolling window optimization. A WCDMA base station planning method based on rolling windows is presented, where the global optimization problem is decomposed into small scale optimization problems in rolling windows. An effective shifting strategy is designed to move the windows in two-dimensional space, and the inter-interference in WCDMA networks is predicted for each rolling window. It is proved that our method keeps the global objective of the original problem non-increasing during optimization. In simulation, three different shifting strategies are tested, and the results are analyzed. This paper shows the importance of shifting strategy for rolling windows in two-dimensional space.
Liu, L, Gu, HY & Xi, YG 2006, 'Heuristic method for job shop scheduling based on decomposed due date', Kongzhi yu Juece/Control and Decision, vol. 21, no. 3, pp. 253-257.
A heuristic method for job shop scheduling based on decomposed due date to minimize total weighted tardiness is proposed. The initial due date of each operation is determined according to the flow allowance rate of each job, then the job sequences on all machines are obtained by the improved modified operation due date rule based on Giffler-Thompson scheme. And the due date of the critical operation is adjusted to improve the solution quality with considering interactions among jobs at each iteration. The simulation results show that the proposed method can obtain good solutions with acceptable computational efficiency, and can be used to the real job shop scheduling system.
Zhang, HY, Gu, HY & Xi, YG 2006, 'Planning algorithm for WCDMA base station location problem based on cluster decomposition', Kongzhi yu Juece/Control and Decision, vol. 21, no. 2, pp. 213-216.
An algorithm based on cluster decomposition is presented for large scale WCDMA base station positioning problem. A data matrix based on the signal gain of cellular networks and some criterion functions are designed for K means clustering. In the algorithm, the original problem is firstly decomposed into K sub-problems by K means clustering. Each sub-problem is then solved by integer programming. Finally, the solutions of K sub-problems are coordinated to form an approximate solution of the global problem. Simulation result shows the validity of this algorithm.
Zuo, Y, Gu, H & Xi, Y 2006, 'Modified bottleneck-based procedure for large-scale flow-shop scheduling problems with bottleneck', Chinese Journal of Mechanical Engineering, vol. 19, no. 3, pp. 356-361.
Zuo, Y, Gu, HY & Xi, YG 2006, 'Bottleneck-based decomposition algorithm for large-scale flow shop scheduling problems', Kongzhi yu Juece/Control and Decision, vol. 21, no. 4, pp. 425-429.
A bottleneck-based decomposition heuristic algorithm is proposed for dealing with computational complexity in large-scale flow shop scheduling problems. Based on the characteristic of bottleneck, the flow shop is decomposed into bottleneck and non-bottleneck machines. A single-machine scheduling problem with release time and delivery time is built for the bottleneck machine, which is solved optimally, while simple priority rules are used for scheduling the non-bottlenecks. The correlations between the bottleneck and non-bottleneck machines are coordinated by adjusting the release time and delivery time of jobs on the bottleneck machine. Simulation results show that the heuristic algorithm can obtain better solution in quite short time and be suitable to large-scale problems.
Jia, Y, Gu, H & Xi, Y 2005, 'Rolling horizon scheduling algorithm for dynamic vehicle scheduling system', Journal of Southeast University (English Edition), vol. 21, no. 1, pp. 92-96.
Dynamic exclusive pickup and delivery problem with time windows (DE-PDPTW), a special dynamic vehicle scheduling problem, is proposed. Its mathematical description is given and its static properties are analyzed, and then the problem is simplified as the asymmetrical traveling salesman problem with time windows. The rolling horizon scheduling algorithm (RHSA) to solve this dynamic problem is proposed. By the rolling of time horizon, the RHSA can adapt to the problem's dynamic change and reduce the computation time by dealing with only part of the customers in each rolling time horizon. Then, its three factors, the current customer window, the scheduling of the current customer window and the rolling strategy, are analyzed. The test results demonstrate the effectiveness of the RHSA to solve the dynamic vehicle scheduling problem.
Jia, YJ, Gu, HY & Xi, YG 2005, 'Analysis and algorithm of single-vehicle exclusive pickup and delivery problem with time windows', Shanghai Jiaotong Daxue Xuebao/Journal of Shanghai Jiaotong University, vol. 39, no. 3, pp. 409-412.
The exclusive pickup and delivery problem with time windows (E-PDPTW), an NP-hard combinatorial optimization problem existed extensively in the transportation domain, was proposed. The mathematical description of this problem was proposed and its properties were analyzed, and then the problem was simplified as an asymmetric traveling salesman problem (TSP) with time windows. A two-phase quick algorithm to solve single vehicle E-PDPTW was proposed, whose time complexity is only O(n3) and the test results indicate the algorithm is effective and quick.
Liu, Y, Gu, HY & Xi, YG 2005, 'Planning and scheduling algorithm based on TOC for complex hybrid flow shop problems', Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS, vol. 11, no. 1, pp. 97-103.
For complex Hybrid Flow Shop (HFS) problems with reentrance, batch processing, setup-time and multiple optimization objectives, a general description for HFS was presented. And then a planning and scheduling algorithm based on Theory of Constraints (TOC) was proposed. The whole framework of algorithm was based on the five principle steps of TOC. The multiple-objective optimization was realized by using objective programming. The solution was analyzed by computational study. The upper bound was obtained by estimating bottleneck capacity.
Wang, B, Xi, Y & Gu, H 2005, 'Terminal penalty rolling scheduling based on an initial schedule for single-machine scheduling problem', Computers & Operations Research, vol. 32, no. 11, pp. 3059-3072.View/Download from: Publisher's site
Wang, B, Xi, YG & Gu, HY 2005, 'Improved rolling horizon procedure for single-machine scheduling with release times', Kongzhi yu Juece/Control and Decision, vol. 20, no. 3.
A rolling horizon procedure (RHP) is used in solving a kind of single-machine dynamic scheduling problems with release times. An improved sub-problem for the RHP is proposed. A terminal penalty function is appended to the objective of each sub-problem, in which both the local objective and the global objective are considered. It is proved that an existing branch and bound can be revised to solve the improved sub-problem. Computational results demonstrate that the improved RHP performs better than the best dispatching rule on most cases.
Xiong, J, Gu, H & Xi, Y 2005, 'UML-based simulation software design about hybrid flow shop manufacturing system', Jisuanji Gongcheng/Computer Engineering, vol. 31, no. 5.
As a standard modeling language, unify modeling language (UML) has widely used in many application fields where focus on software design and analysis. By designing HFS simulation software with UML in this article, the design process of software based on UML can be described, and at the same time some questions such as how it supports OO technology and how to realize software architecture will be depicted completely. At last with the accomplishment of an example related this design idea more futures in UML application is given.
Zhang, H, Xi, Y & Gu, H 2005, 'A decomposition and coordination scheduling method for flow shop problem based on TOC', ACTA AUTOMATICA SINICA, vol. 31, no. 2, pp. 182-187.
Jia, YJ, Gu, HY & Xi, YG 2004, 'Quick taboo search algorithm for solving PDPTW problem', Kongzhi yu Juece/Control and Decision, vol. 19, no. 1, pp. 57-60.
A quick taboo search algorithm is proposed to solve the pickup and delivery problem with time windows (PDPTW) with the reality scale and complexity. The approach is composed of two parts: creating the initial solution and improving the solution. In the first phase, the insert algorithm is used to create the initial solution and in the second phase, the taboo search is applied to improve the solution. Two cases with the reality scale and complexity are created to test the algorithm. The results indicate that the proposed algorithm is effective and quick to solve such PDPTW problems.
Li, L, Gu, H & Chen, J 2003, 'Insertion heuristic algorithm in complex PDPTW problem', Jisuanji Gongcheng/Computer Engineering, vol. 29, no. 16, p. 65.
Li, L, Chen, J & Gu, HY 2002, 'Insertion heuristic in multi-vehicle pickup and delivery problem with time window', Shanghai Jiaotong Daxue Xuebao/Journal of Shanghai Jiaotong University, vol. 36, no. SUPPL., pp. 99-101.
This paper foucsed on the insertion heuristics which are commonly used for the tour construction in multi-vehicle pickup and delivery problem with time window (m-PDPTW). It analyzed the factors that may impact the quality of solution from several aspects and put forward three criteria to direct the process of insertion. Based on it, an improved insertion heuristic was advanced, which is an extension of the Solomon's VRPTW insertion heuristic. The computational results prove that the improved insertion heuristic can eliminate the disadvantage of simple insertion heuristics and improve the quality of initial solution greatly.
Han-yu, G & Chen, CHEN 2000, 'A new algorithm for the computation of low frequency electro-mechanical oscillation modes of large power systems', PROCEEDINGS-CHINESE SOCIETY OF ELECTRICAL ENGINEERING, vol. 20, pp. 50-54.
Xi, Y & Gu, H 1998, 'Feasibility analysis and soft constraints adjustment of CMMO', ACTA AUTOMATICA SINICA, vol. 24, pp. 727-732.
Gu, H, Schutt, A, Stuckey, P, Wallace, M & Chu, G 2015, 'Exact and Heuristic Methods for the Resource-Constrained Net Present Value Problem' in Schwindt, C & Zimmermann, J (eds), Handbook on Project Management and Scheduling, Springer, Switzerland, pp. 299-318.
Gu, H & Lam, HC 2019, 'A Genetic Algorithm Approach for Scheduling Trains Maintenance Under Uncertainty', International Conference on Computer Science, Applied Mathematics and Applications, Springer, Cham, Hanoi, Vietnam, pp. 106-118.View/Download from: Publisher's site
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: Publisher's site
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: 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: Publisher's site
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.
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: Publisher's site
© 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: Publisher's site
© 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: Publisher's site
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.
Gu, H 2016, 'Local Cuts for 0–1 Multidimensional Knapsack Problems', Data and Decision Sciences in Action, Australian Society for Operations Research Conference, Springer, Canberra, Australia, pp. 81-89.View/Download from: Publisher's site
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: Publisher's site
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.
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: Publisher's site
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.
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.
Czibula, O, Gu, H, Russell, A & Zinder, Y 2014, 'A multi-stage IP-based heuristic for class timetabling and trainer rostering', PATAT 2014 - Proceedings of the 10th International Conference on the Practice and Theory of Automated Timetabling, pp. 102-127.
© PATAT 2014 - Proceedings of the 10th International Conference on the Practice and Theory of Automated Timetabling. All rights reserved. We consider an academic 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 (ILP) 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 more flexible regarding constraints and objectives, and is able to generate solutions of superior quality to the existing software system in use at the organisation.
Gu, H, Schutt, A & Stuckey, P 2013, 'A Lagrangian Relaxation Based Forward-Backward Improvement Heuristic for Maximising the Net Present Value of Resource-Constrained Projects', Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems, Springer, Yorktown Heights, NY, pp. 340-346.View/Download from: Publisher's site
Gu, H, Stuckey, P & Wallace, M 2012, 'Maximising the net present value of large resource-constrained projects', Principles and Practice of Constraint Programming - CP 2012, International Conference on Principles and Practice of Constraint Programming, Springer, Québec City, QC, Canada, pp. 767-781.View/Download from: Publisher's site
Gu, H, Wallace, Mark.G. & Stuckey, Peter.J. 2012, 'An improved Lagrangian relaxation method for maximising the net present value of large resource-constrained projects', The 20th International Symposium on Mathematical Theory of Networks and Systems (MTNS 2012), International Symposium on the Mathematical Theory of Networks and Systems, Melbourne, Victoria.
Gu, H & Evans, I 2011, 'Study on Improving Solution Regularity for Crew Pairing Problems', 2011 IFORS Conference on World OR : Global Economy and Sustainable Environment, Melbourne, Australia.
When producing optimised crew pairings to cover airline schedules, many airlines consider that regular pairings are easier to implement and manage, and are to be preferred if there is limited cost impact. In this paper we propose a column generation based solution approach to consider regularity, which is regarded as the repeatability of pairings in the planning horizon, as well as cost. The contributions of our method include the use of a fully dated model, an improved k-shortest path pricing algorithm and comprehensive computational results for a schedule from a large Asian airline.
Gu, H, Xi, Y & Tao, J 2007, 'Randomized Lagrangian heuristic based on Nash equilibrium for large scale single machine scheduling problem', Intelligent Control, 2007. ISIC 2007, IEEE, Singapore, pp. 464-468.
Liu, L, Gu, H & Xi, Y 2005, 'An iterative algorithm for job shop scheduling based on adjusting due date', Proceedings of the 24th Chinese Control Conference, Vols 1 and 2, 24th Chinese Control Conference, SOUTH CHINA UNIV TECHNOLOGY PRESS, Canton, PEOPLES R CHINA, pp. 1214-1217.
Zuo, Y, Gu, H & Xi, Y 2005, 'Prioritizing sub-problem in shifting bottleneck procedure for job shop scheduling', PROCEEDINGS OF THE 24TH CHINESE CONTROL CONFERENCE, VOLS 1 AND 2, 24th Chinese Control Conference, SOUTH CHINA UNIV TECHNOLOGY PRESS, Canton, PEOPLES R CHINA, pp. 1195-1198.
Wang, B, Xi, Y & Gu, H 2004, 'Rolling horizon heuristic for single-machine scheduling problem', Proceedings of the World Congress on Intelligent Control and Automation (WCICA), pp. 2872-2876.
A kind of rolling horizon heuristic for the scheduling problems with globally known information was presented. Under the heuristic the scheduling problems were addressed by using a series of locally scheduling instead of a single globally off-line scheduling. At each decision time, a subproblem based on a job subset was particularly defined and the sizes of sub-problems were limited. The sub-problem for locally scheduling was solved and then a portion of the solution was implemented. While the decision time was being put forward, global schedule was being realized step by step. Usually it is hard to analyze the global performance of rolling horizon procedures due to heuristic. However, a terminal penalty function was appended to the objective function of sub-problems to make the local objective consistent with the global one. Global performances of rolling horizon procedures can be analyzed to an extent. Several conclusions were drawn out about the global performance of the new rolling horizon procedures. The procedural global performance is getting better and better from one decision time to another and the performance of the initial schedule is an upper bound for that of the ultimately realized schedule.
Hanyu, G & Chen, C 1998, 'Improving refactored bi-iteration method for small signal stability analysis of large power systems', Power System Technology, 1998. Proceedings. POWERCON'98. 1998 International Conference on, IEEE, pp. 1417-1420.