We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution … Read more
This paper is devoted to the approximate resolution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact resolution methods, extensive computational results demonstrating its practical … Read more
This paper is devoted to the study of a resource-constrained scheduling problem which arises in relation to the operability of certain high availability real-time distributed systems. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the … Read more
This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process … Read more
This paper addresses the general single-machine earliness-tardiness problem with distinct release dates, due dates, and unit costs. The aim of this research is to obtain an exact nonpreemptive solution in which machine idle time is allowed. In a hybrid approach, we formulate and then solve the problem using dynamic programming (DP) while incorporating techniques from … Read more
This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules. … Read more
We describe scheduling algorithms for monitoring an information source whose contents change at times modeled by a nonhomogeneous Poisson process. In a given time period of length T, we enforce a politeness constraint that we may only probe the source at most n times. This constraint, along with an optional constraint that no two probes … Read more
We present a compact linearization for a broad class of bilinear 0-1 mixed-integer problems subject to assignment constraints. We apply the linearization to three classes of problems: quadratic assignment, multiprocessor scheduling with communication delays, and graph partitioning, and show that it yields faster solution times. Citation DEI, Politecnico di Milano, Working paper, April 2005. Article … Read more
This paper is devoted to basic scheduling problems in which the scheduling cost of a job is not a function of its completion time. Instead, the cost is derived from the integration of a cost function over the time intervals on which the job is processed. This criterion is specially meaningful when job preemption is … Read more
We study a single-machine sequencing problem with both release dates and deadlines to minimize the total weighted completion time. We propose a branch-and-bound algorithm for this problem. The algorithm exploits an effective lower bound and a dynamic programming dominance technique. As a byproduct of the lower bound, we have developed a new algorithm for the … Read more