Kellerer, Hans and Strusevich, Vitaly (2013) Fast approximation schemes for Boolean programming and scheduling problems related to positive convex Half-Product. European Journal of Operational Research, 228 (1). pp. 24-32. ISSN 0377-2217 (doi:https://doi.org/10.1016/j.ejor.2012.12.028)

Preview

PDF (AAM) 10124_STRUSEVICH_EJOR__(AAM)_(2013).pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (246kB)

Abstract

We address a version of the Half-Product Problem and its restricted variant with a linear knapsack constraint. For these minimization problems of Boolean programming, we focus on the development of fully polynomial-time approximation schemes with running times that depend quadratically on the number of variables. Applications to various single machine scheduling problems are reported: minimizing the total weighted flow time with controllable processing times, minimizing the makespan with controllable release dates, minimizing the total weighted flow time for two models of scheduling with rejection.

Item Type:	Article
Additional Information:	[1] NOTICE: this is the author’s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, Volume 228, Issue 1, (2013) DOI 10.1016/j.ejor.2012.12.028. [2] This research was supported by the EPSRC funded project P/I018441/1 “Quadratic and Linear Knapsack Problems with Scheduling Applications”.
Uncontrolled Keywords:	scheduling, Half-Product, quadratic knapsack, scheduling with rejection, scheduling with controllable processing times, FPTAS
Subjects:	Q Science > QA Mathematics
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Related URLs:	Publisher Organisation
Last Modified:	14 Oct 2016 14:44
URI:	http://gala.gre.ac.uk/id/eprint/10124

Actions (login required)

View Item

Downloads