We investigate a variant of the classic knapsack problem in the context of single-machine scheduling with controllable processing times under a makespan constraint. In this problem, the processing time of each job is a bounded linear decreasing function of the amount of resource allocated to its job processing operation. The task is to choose some jobs for processing with the goal to maximize the total profit while satisfying a given makespan constraint, where the total profit is the total revenue minus the total resource consumption cost. We show that the studied problem is NP-hard. By exploring the structural properties on the optimal solution, we propose a constant factor approximation algorithm with a performance ratio of $$\frac{1}{5}$$ 1 5 . Subsequently, we design a dynamic programming exact algorithm and a fully strongly polynomial time approximation scheme.
Guo, Yanjie, Luo, Wenchang. Single-machine scheduling with rejection and controllable processing times to maximize profit under a makespan constraint. // Journal of Scheduling. – 2026. – DOI: 10.1007/s10951-026-00878-z. – URL: http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00878-z
Guo, Yanjie, Luo, & Wenchang (2026). Single-machine scheduling with rejection and controllable processing times to maximize profit under a makespan constraint. Journal of Scheduling. https://doi.org/10.1007/s10951-026-00878-z
Guo, et al. “Single-machine scheduling with rejection and controllable processing times to maximize profit under a makespan constraint.” Journal of Scheduling, 2026. doi:10.1007/s10951-026-00878-z.
@article{Guo2026,
title = {Single-machine scheduling with rejection and controllable processing times to maximize profit under a makespan constraint},
author = {Guo and Yanjie and Luo and Wenchang},
journal = {Journal of Scheduling},
year = {2026},
doi = {10.1007/s10951-026-00878-z},
url = {http://link.springer.com/openurl/fulltext?id=doi:10.1007/s10951-026-00878-z}
}
In this paper, we consider cost-sharing problems defined on rooted trees. We refer to these problems as cost-tree problems and to the induced transferable utility cooperative games as irrigation games. We introduce a formal notion of...
In this paper, we focus on nonlinear programming problems with cardinality constraints that restrict the number of nonzero components of the decision vector. We start with a straightforward mixed-integer programming reformulation....
Portfolio selection is a critical issue in financial management under uncertainty. In this paper, we propose a complex approach for portfolio selection with quantile return approximation. In particular, we propose a practical workflow...
The transcendental logarithmic (translog) production function is recognised as a flexible functional form for modelling production processes. It accommodates varying elasticities of input substitution and diverse types of...
This study investigates mothership-drone route determination using two optimization approaches: a Mixed Integer Linear Programming (MILP) model based on a discrete hexagonal grid, and a Mixed Integer Nonlinear Programming (MINLP) model...