Multidimensional tropical optimization problems with applications to job scheduling

Research output

Abstract

Optimization problems are considered which are formulated and solved in the tropical mathematics setting. The problems are to minimize or maximize functions defined on vectors of finite dimensional semimodules over idempotent semifields, subject to linear inequality and equality constraints. The objective functions can be linear or take the form of non-linear functions calculated by using a conjugate transposition of vectors. We give an overview of known problems and briefly discuss available solution methods. Furthermore, recent results on the solution of certain new problems are presented which give the problems direct explicit solutions in a compact vector form. We apply the obtained results to solve scheduling problems for a set of jobs operating under various precedence relations in the form of start-start, start-finish, early-start, late-finish and other temporal constraints. The problems are formulated to find optimal schedules according to certain optimality criteria, which involve the minimization of the maximum deviation of job completion times from given due dates, the minimization and maximization of the maximum deviation time between job completion times, and the minimization of the maximum job flow (processing) time.
Original languageEnglish
Pages50
Publication statusPublished - 2014
EventAPMOD 2014 International Conference on Applied Mathematical Optimization and Modelling - England, Warwick
Duration: 9 Apr 201411 Apr 2014
http://www2.warwick.ac.uk/fac/soc/wbs/conf/apmod2014/program/booklet.pdf

Conference

ConferenceAPMOD 2014 International Conference on Applied Mathematical Optimization and Modelling
CountryUnited Kingdom
CityWarwick
Period9/04/1411/04/14
Internet address

Fingerprint

Job Scheduling
Optimization Problem
Completion Time
Deviation
Semimodule
Semifield
Temporal Constraints
Due Dates
Transposition
Optimality Criteria
Equality Constraints
Linear Constraints
Inequality Constraints
Explicit Solution
Nonlinear Function
Idempotent
Scheduling Problem
Linear Inequalities
Schedule
Objective function

Scopus subject areas

  • Mathematics(all)

Cite this

Krivulin, N. (2014). Multidimensional tropical optimization problems with applications to job scheduling. 50. Abstract from APMOD 2014 International Conference on Applied Mathematical Optimization and Modelling, Warwick, .
Krivulin, N. / Multidimensional tropical optimization problems with applications to job scheduling. Abstract from APMOD 2014 International Conference on Applied Mathematical Optimization and Modelling, Warwick, .
@conference{af7e8265ed2945bb9a40a8eafc1b18b8,
title = "Multidimensional tropical optimization problems with applications to job scheduling",
abstract = "Optimization problems are considered which are formulated and solved in the tropical mathematics setting. The problems are to minimize or maximize functions defined on vectors of finite dimensional semimodules over idempotent semifields, subject to linear inequality and equality constraints. The objective functions can be linear or take the form of non-linear functions calculated by using a conjugate transposition of vectors. We give an overview of known problems and briefly discuss available solution methods. Furthermore, recent results on the solution of certain new problems are presented which give the problems direct explicit solutions in a compact vector form. We apply the obtained results to solve scheduling problems for a set of jobs operating under various precedence relations in the form of start-start, start-finish, early-start, late-finish and other temporal constraints. The problems are formulated to find optimal schedules according to certain optimality criteria, which involve the minimization of the maximum deviation of job completion times from given due dates, the minimization and maximization of the maximum deviation time between job completion times, and the minimization of the maximum job flow (processing) time.",
author = "N. Krivulin",
note = "APMOD 2014: International Conference on Applied Mathematical Optimization and Modelling, The University of Warwick, April 09– 11, 2014. Program; APMOD 2014 International Conference on Applied Mathematical Optimization and Modelling ; Conference date: 09-04-2014 Through 11-04-2014",
year = "2014",
language = "English",
pages = "50",
url = "http://www2.warwick.ac.uk/fac/soc/wbs/conf/apmod2014/program/booklet.pdf",

}

Multidimensional tropical optimization problems with applications to job scheduling. / Krivulin, N.

2014. 50 Abstract from APMOD 2014 International Conference on Applied Mathematical Optimization and Modelling, Warwick, .

Research output

TY - CONF

T1 - Multidimensional tropical optimization problems with applications to job scheduling

AU - Krivulin, N.

N1 - APMOD 2014: International Conference on Applied Mathematical Optimization and Modelling, The University of Warwick, April 09– 11, 2014. Program

PY - 2014

Y1 - 2014

N2 - Optimization problems are considered which are formulated and solved in the tropical mathematics setting. The problems are to minimize or maximize functions defined on vectors of finite dimensional semimodules over idempotent semifields, subject to linear inequality and equality constraints. The objective functions can be linear or take the form of non-linear functions calculated by using a conjugate transposition of vectors. We give an overview of known problems and briefly discuss available solution methods. Furthermore, recent results on the solution of certain new problems are presented which give the problems direct explicit solutions in a compact vector form. We apply the obtained results to solve scheduling problems for a set of jobs operating under various precedence relations in the form of start-start, start-finish, early-start, late-finish and other temporal constraints. The problems are formulated to find optimal schedules according to certain optimality criteria, which involve the minimization of the maximum deviation of job completion times from given due dates, the minimization and maximization of the maximum deviation time between job completion times, and the minimization of the maximum job flow (processing) time.

AB - Optimization problems are considered which are formulated and solved in the tropical mathematics setting. The problems are to minimize or maximize functions defined on vectors of finite dimensional semimodules over idempotent semifields, subject to linear inequality and equality constraints. The objective functions can be linear or take the form of non-linear functions calculated by using a conjugate transposition of vectors. We give an overview of known problems and briefly discuss available solution methods. Furthermore, recent results on the solution of certain new problems are presented which give the problems direct explicit solutions in a compact vector form. We apply the obtained results to solve scheduling problems for a set of jobs operating under various precedence relations in the form of start-start, start-finish, early-start, late-finish and other temporal constraints. The problems are formulated to find optimal schedules according to certain optimality criteria, which involve the minimization of the maximum deviation of job completion times from given due dates, the minimization and maximization of the maximum deviation time between job completion times, and the minimization of the maximum job flow (processing) time.

M3 - Abstract

SP - 50

ER -

Krivulin N. Multidimensional tropical optimization problems with applications to job scheduling. 2014. Abstract from APMOD 2014 International Conference on Applied Mathematical Optimization and Modelling, Warwick, .