Search

We study an operation scheduling problem where a finite set of jobs with due dates must be completed by one machine: each job is completed as soon as a specific subset of unit operations is done. Distinct jobs may share operations, and when an operation is done, it is done for all the jobs that share it. The goal is to schedule operations so that the weighted number of tardy jobs is minimized. We reformulate the problem as maximum stable set problem on a special graph and study its structure. Valid inequalities and optimality cuts are derived, separated, and tested in a computational experience that identifies some features of hard instances and the potential contribution of the addition, at root, of various cut classes. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 644, 306-320 2014

This article addresses the problem of allocating users to radio resources in the downlink of an OFDMA cellular system. We consider a classical multicellular environment with a realistic interference model and a margin adaptive approach, i.e., we aim at minimizing total transmission power while maintaining a certain given rate for each user. We discuss computational complexity issues of the resulting model and present a heuristic approach that finds optima under suitable conditions or reasonably good solutions in the general case. Computational experiments show the effectiveness of the proposed heuristic in a comparison with both a commercial state-of-the-art optimization solver and other approaches from the literature. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011 © 2011 Wiley Periodicals, Inc.

We investigate polyhedral properties of the following scheduling problem: given two sets of unit, indivisible jobs and revenue functions of the jobs completion times, find a one-machine schedule maximizing the total revenue under the constraint that the schedule of each job set respects a prescribed chain-like precedence relation. A solution to this problem is an order preserving assignment of the jobs to a set of time-slots. We study the convex hull of the feasible assignments and provide families of facet-defining inequalities in two cases: (i) each job must be assigned to a time-slot and (ii) a job does not need to be assigned to any time-slot. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011 © 2011 Wiley Periodicals, Inc.

This article investigates a two-user competitive scheduling problem. The problem arises in a Universal Mobile Telecommunication System (UMTS) developed within the European IST project FUTURE: given two mobile terminals, one wants to maximize the on-time data packets transmitted to one user, while guaranteeing a certain amount of on-time data packets to the other. We show that the problem is NP-hard, despite peculiar properties of data and solutions. We propose a fast lagrangian heuristic able to cope with a severe real-time requirement, and compare it to a greedy-like heuristic on a set of practical instances. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 132–141 2004