We investigate a family of single-machine scheduling problems that combine convex resource consumption with job rejection, where the performance measure is the total completion time of the accepted jobs. Across four natural variants-distinguished by whether the resource consumption cost and rejection cost appear in the objective or as budget constraints-we analyze their computational complexity and develop efficient algorithms. We show that one variant is polynomially solvable, two variants are weakly NP-hard but admit fully polynomial-time approximation schemes (FPTASs), and the remaining variant admits an FPTAS while its exact complexity remains open.

SUMMARY Cloud computing provides infrastructure, platform and software as services to customers. For the purpose of providing reliable and truthful service, a fair and elastic resource allocation strategy is essential from the standpoint of service customers. In this paper, we propose a game theoretic mechanism for dynamic cloud service management, including task assignment and resource allocation to provide reliable and truthful cloud services. A user utility function is first devised considering the dynamic characteristics of cloud computing. The elementary stepwise system is then applied to efficiently assign tasks to cloud servers. A resource allocation mechanism based on bargaining game solution is also adopted for fair resource allocation in terms of quality of service of requested tasks. Through numerical experiments, it is shown that the proposed mechanism guarantees better system performance than several existing methods. The experimental results show that the mechanism completes the requested tasks earlier with relatively higher utility while providing a significant level of fairness compared with existing ones. The proposed mechanism is expected to support cloud service providers in elastically managing their limited resources in a cloud computing environment in terms of quality of service. Copyright © 2013 John Wiley & Sons, Ltd.

Abstract In batch production systems, multiple items can be processed in the same batch if they share sufficiently similar production parameters. We consider the batch consolidation problem of minimizing the number of batches of a finite set of items. This article focuses on the case in which only one or two items can be processed in a single batch. The problem is NP ‐hard and cannot be approximated within 1.0021 of the optimum under the premise, P≠NP. However, the problem admits a ${{3}\over{2}}$ ‐approximation. The idea is to decompose the demands of items so that a maximum matching in the graph on the vertices of the decomposed demands provides a well‐consolidated batch set. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 12–19 2011