Premium
Determining optimal sizes of bounded batches with rejection via quadratic min‐cost flow
Author(s) -
Mosheiov Gur,
Strusevich Vitaly A.
Publication year - 2017
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21740
Subject(s) - bounded function , mathematical optimization , quadratic equation , regular polygon , scheduling (production processes) , upper and lower bounds , function (biology) , minimum cost flow problem , computer science , flow (mathematics) , mathematics , flow network , mathematical analysis , geometry , evolutionary biology , biology
In this article, we consider a single machine scheduling problem, in which identical jobs are split into batches of bounded sizes. For each batch, it is allowed to produce less jobs than a given upper bound, that is, some jobs in a batch can be rejected, in which case a penalty is paid for each rejected job. The objective function is the sum of several components, including the sum of the completion times, total delivery cost, and total rejection cost. We reduce this problem to a min‐cost flow problem with a convex quadratic function and adapt Tamir's algorithm for its solution. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 217–224, 2017