Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function

Dvir Shabtay and Moshe Kaspi

Naval Research Logistics (NRL), 2006, vol. 53, issue 3, 204-216

Abstract: We consider open‐shop scheduling problems where operation‐processing times are a convex decreasing function of a common limited nonrenewable resource. The scheduler's objective is to determine the optimal job sequence on each machine and the optimal resource allocation for each operation in order to minimize the makespan. We prove that this problem is NP‐hard, but for the special case of the two‐machine problem we provide an efficient optimization algorithm. We also provide a fully polynomial approximation scheme for solving the preemptive case. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006

Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/nav.20133

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:53:y:2006:i:3:p:204-216

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().