Optimisation and Scheduling

Objectives and Syllabus

Provides an understanding of the underlying principles of optimisation in relation to the various techniques used for realising optimisers and schedulers. Topics covered include the formulation of optimisation problems; equalities, constraints and objective functions: least squares and regression: linear programming; concepts of LP, simplex method, sensitivity and duality: unidirectional optimisation; continuity, constrained and unconstrained functions, Newton’s method, quadratic approximation and interpretation: multivariable optimisation; direct and indirect methods, finite difference approximations: non-linear programming (NLP); quadratic programming, penalty functions, sequential recursive programming (SQP), optimisation of dynamic processes: real-time optimisation; structure of optimisers, steady state models, technical requirements, interface with control system, calibration, checks for convergence: sequential processes; formulation of objectives, project evaluation and review technique (PERT), critical path methods (CPM), dynamic programming, mixed integer linear programming (MILP) & non-linear programming (MINLP), branch and bound, genetic algorithms, biological analogies, concepts of evolutionary computing, chromosome representation, genetic operators, multi-objective genetic algorithms (MOGA).

Case studies and PC based exercises are used to familiarise students with the application of these methods to practical optimisation and scheduling problems.

Aims

To provide an in-depth understanding of the principles underlying various techniques of optimisation and scheduling, real-time or otherwise, and to develop a grasp of the issues involved in applying them in the process industry.

Objectives

• To appreciate the distinction between and essential characteristics of steady state optimisers and dynamic optimising controllers. 
• To develop a quantitative understanding of the principles of optimisation and scheduling. 
• To become familiar with a range of optimisation and scheduling techniques, such as the use of LP, QP and GA methods. 
• To appreciate how optimisers and schedulers handle objectives, physical and operational constraints. 
• To develop a feel for the realisation of optimisers and schedulers, both real-time and off-line, in an industrial context. 
• To appreciate the functionality of proprietary industrial optimisers and schedulers.

Phasing

Prerequisite to this module are the Modelling and Simulation (CME 8380) and Modern Control Systems Design (CME 8382) modules.

Study Modes

This module is of one week's full-time intensive study consisting of a variety of lectures, informal tutorials for problem solving, structured computer-based laboratory work and demonstrations.  It is followed by an assignment to be carried out in the student’s own time.

Coursework

The time allocation for practical work provides for Excel and/or Matlab based demonstrations and exercises designed to reinforce the taught materials.  These include use of the Optimisation toolbox.

Recommended Texts

• Edgar T F, Himmelblau D M & Lasdon L S,  Optimisation of Chemical Processes,  2nd Edition,  McGraw Hill,  2001 
• Gill E G, Murray W & Wright M H,  Practical Optimisation,  Academic Press,  1986. 
• Love J,  Process Automation Handbook,  Springer, 2007
• MATLAB Optimisation Toolbox Handbook.

Topics Included

Introduction:  The nature of optimisation.  Characteristics of optimisation problems.  Distinction between optimisers and optimal control.  Distinction between optimisation and scheduling.  Concept and formulation of the objective function.  The nature of constraints.

Linear programming (LP):  Basic concepts of LP.  Formulation of LP models.  Linear constraints.  Feasible solution space.  Use of the simplex method.  Standard LP form.  Worked example.  Use of tableau.  Formulation of objectives in terms of throughput, delivery dates, plant utilisation, etc.  Integer and mixed integer linear programming (MILP).  Branch and bound.  Mixed integer non-linear programming (MINLP).  Demonstration of proprietary scheduling system.

Unconstrained optimisation:  Continuity of functions.  Global and local maxima: one and two dimensional problems.  Newton’s method and the quadratic approximation.  Search direction and search procedures.  Steepest descent and the Levenberg Marquart algorithm.  Line searching and step length.  Brent’s and Newton Raphson’s methods.  Worked examples.

Constrained optimisation:  The Lagrangian multiplier.  Generalised Lagrangian functions.  Equality and inequality constraints.  Inactive constraints and slack variables.  Worked examples.  Sensitivity analysis.  Kuhn-Tucker conditions.  Quadratic programming (QP).  Recursive form of QP and sequential quadratic programming (SQP).  Reduced gradient methods and penalty functions.  Worked examples.

Real-time optimisers (RTO):  Costs, benefits and justification.  Classification of RTOs into steady state optimisers (SSO) and dynamic optimising controllers (DOC).  Structure of SSOs.  Steady state models for SSOs.  Methodology for steady state optimisation.  Steady state detection.  Model updating.  SQP solution of the steady state problem.  Demonstration of proprietary SSO.  Structure of DOCs.  Formulation and handling of constraints by DOCs.  QP solution of the dynamic problem.  Application of DOCs.  Interface between DOC and model predictive controller (MPC).  Demonstration of proprietary DOC.

Genetic algorithms (GA):  Biological analogies.  Concepts of evolutionary computing.  Formulation of problem.  Chromosome representation: objectives, data, constraints, etc.  Genetic operators: eg cross-over and mutation.  Population control and fitness.  Multi-objective genetic algorithms (MOGA).  Demonstration of the use of GA for optimising and scheduling problems.