This paper addresses a single machine total weighted tardiness (TWT) batch-scheduling problem in which jobs have release dates, nonidentical sizes, and are compatible between each other. We propose two integer linear programming models: the first one is a time-indexed formulation (TIF), and the second is an innovative time-size-indexed formulation (TSIF). Although TIF clearly outperforms the existing formulation for the problem, TSIF is capable of producing much stronger bounds in practice. The latter also enables us to develop an efficient column-generation (CG) algorithm. The pricing subproblem corresponds to a resource-constrained shortest path problem that is solved using a bucket graph–based labeling algorithm. The solutions of such a subproblem may contain cycles (reprocessing of jobs), and thus, a memory mechanism called dynamic arc-based ng-sets is employed in the labeling with a view toward avoiding some of them. Moreover, we also implement a preprocessing scheme based on Lagrangian relaxation to perform variable fixing. Extensive computational experiments were carried out in 810 benchmark instances. The proposed CG algorithm is capable of solving instances with up to 100 jobs to optimality. In addition, we believe that this is the first exact approach for a TWT batch-scheduling variant capable of systematically solving instances with up to 50 jobs. High-quality results are also reported for three special cases of the problem—more precisely, when (i) the penalty weights are unitary, (ii) there are no release dates, and (iii) all due dates are set to zero and, hence, the objective becomes equivalent to minimizing the weighted completion time. Summary of Contribution: This paper provides the first exact algorithm for a standard variant of a batch-scheduling total weighted tardiness problem that can solve instances with up to 100 jobs to optimality, a considerable leap with respect to previous works. In particular, we propose a time-indexed formulation that has the advantage of being relatively simple to implement, and yet we show that it is not theoretically dominated by the other innovative formulation proposed in the paper referred to as the time-size-indexed formulation (TSIF). Moreover, we present a Lagrangian approach to quickly fix variables and an iterative column-generation (CG) procedure over a Dantzig–Wolfe decomposition of TSIF that combines an efficient pricing algorithm with a dynamic scheme to adjust the subproblem constraints. The proposed CG approach is capable of producing very strong bounds for the problem as well as for some of its special cases.

This article deals with the bi‐objective pollution‐routing problem (bPRP), a vehicle routing variant that arises in the context of green logistics. The two conflicting objectives considered are the minimization of the CO2 emissions and the costs related to driver's wages. A multi‐objective approach based on the two‐phase Pareto local search heuristic is employed to generate a good approximation of the Pareto front. During the first phase of the method, a first set of potentially efficient solutions is obtained by solving a series of weighted sum problems with an efficient heuristic originally developed to solve the single‐objective PRP. A dichotomous scheme is used to generate the different weight sets in an automatic way. In the second phase, the set is improved with an efficient Pareto local search (PLS) procedure. The use of PLS allows to limit the number of computational demanding weighted sum problems solved in the first phase, while keeping high‐quality results. Extensive computational experiments over existing benchmark instances show that the proposed approach leads to better results in less CPU time when compared to those obtained by state‐of‐the‐art methods.

This paper addresses the close-enough traveling salesman problem. In this problem, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose a simple yet effective exact algorithm, based on branch-and-bound and second order cone programming. The proposed algorithm was tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider instances both in two- and three-dimensional space.