<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.0 20120330//EN" "JATS-journalpublishing1.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" article-type="research-article">
<front>
<journal-meta>
<journal-id journal-id-type="publisher-id">INFORMATICA</journal-id>
<journal-title-group><journal-title>Informatica</journal-title></journal-title-group>
<issn pub-type="epub">0868-4952</issn><issn pub-type="ppub">0868-4952</issn>
<publisher>
<publisher-name>VU</publisher-name>
</publisher>
</journal-meta>
<article-meta>
<article-id pub-id-type="publisher-id">INFO1083</article-id><article-id pub-id-type="doi">10.15388/Informatica.2016.101</article-id>
<article-categories><subj-group subj-group-type="heading">
<subject>Research Article</subject></subj-group></article-categories>
<title-group>
<article-title>A Maximization Problem in Tropical Mathematics: A Complete Solution and Application Examples</article-title>
</title-group>
<contrib-group>
<contrib contrib-type="Author">
<name><surname>Krivulin</surname><given-names>Nikolai</given-names></name><email xlink:href="mailto:nkk@math.spbu.ru">nkk@math.spbu.ru</email><xref ref-type="aff" rid="j_INFORMATICA_aff_000"/>
</contrib>
<aff id="j_INFORMATICA_aff_000">Faculty of Mathematics and Mechanics, Saint Petersburg State University, 28 Universitetsky Ave., St. Petersburg, 198504, Russia</aff>
</contrib-group>
<pub-date pub-type="epub"><day>01</day><month>01</month><year>2016</year></pub-date><volume>27</volume><issue>3</issue><fpage>587</fpage><lpage>606</lpage><history><date date-type="received"><day>01</day><month>03</month> <year>2014</year></date><date date-type="accepted"><day>01</day><month>06</month> <year>2014</year></date></history>
<permissions><copyright-statement>Vilnius University</copyright-statement><copyright-year>2016</copyright-year></permissions>
<abstract>
<p>An optimization problem is formulated in the tropical mathematics setting to maximize a nonlinear objective function defined by conjugate transposition on vectors in a semimodule over a general idempotent semifield. The study is motivated by problems from project scheduling, where the deviation between completion times of activities is to be maximized subject to precedence constraints. To solve the unconstrained problem, we establish an upper bound for the function, and then obtain a complete solution to a system of vector equations to find all vectors that yield the bound. An extension of the solution to handle constrained problems is discussed. The results are applied to give direct solutions to the motivational problems, and illustrated with numerical examples.</p>
</abstract>
<kwd-group>
<label>Keywords</label>
<kwd>tropical mathematics</kwd>
<kwd>idempotent semifield</kwd>
<kwd>optimization problem</kwd>
<kwd>nonlinear objective function</kwd>
<kwd>project scheduling</kwd>
</kwd-group>
</article-meta>
</front>
</article>
