The paper proposes a new exact approach, based on a Branch, Bound, and Remember (BB&R) algorithm that uses the Cyclic Best First Search (CBFS) strategy, for the 1|r (i) |aU (i) scheduling problem, a single machine...
详细信息
The paper proposes a new exact approach, based on a Branch, Bound, and Remember (BB&R) algorithm that uses the Cyclic Best First Search (CBFS) strategy, for the 1|r (i) |aU (i) scheduling problem, a single machine scheduling problem, where the objective is to find a schedule with the minimum number of tardy jobs. The search space is reduced using new and improved dominance properties and tighter upper bounds, based on a new dynamic programming algorithm. Computational results establish the effectiveness of the BB&R algorithm with CBFS for a broad spectrum of problem instances. In particular, this algorithm was able to solve all problems instances, up to 300 jobs, while existing best known algorithms only solve problems instances up to 200 jobs. Furthermore, the BB&R algorithm with CBFS runs one to two orders of magnitude faster than the current best known algorithm on comparable instances.
This paper presents a Branch, Bound, and Remember (BB&R) exact algorithm using the Cyclic Best First Search (CBFS) exploration strategy for solving the scheduling problem, a single machine scheduling problem with ...
详细信息
This paper presents a Branch, Bound, and Remember (BB&R) exact algorithm using the Cyclic Best First Search (CBFS) exploration strategy for solving the scheduling problem, a single machine scheduling problem with sequence dependent setup times where the objective is to find a schedule with minimum total tardiness. The BB&R algorithm incorporates memory-based dominance rules to reduce the solution search space. The algorithm creates schedules in the reverse direction for problems where fewer than half the jobs are expected to be tardy. In addition, a branch and bound algorithm is used to efficiently compute tighter lower bounds for the problem. This paper also presents a counterexample for a previously reported exact algorithm in Luo and Chu (Appl Math Comput 183(1):575-588, 2006) and Luo et al. (Int J Prod Res 44(17):3367-3378, 2006). Computational experiments demonstrate that the algorithm is two orders of magnitude faster than the fastest exact algorithm that has appeared in the literature. Computational experiments on two sets of benchmark problems demonstrate that the CBFS search exploration strategy can be used as an effective heuristic on problems that are too large to solve to optimality.
This paper presents a modified Branch and Bound (B&B) algorithm called, the Branch, Bound, and Remember (BB&R) algorithm, which uses the Distributed Best First Search (DBFS) exploration strategy for solving th...
详细信息
This paper presents a modified Branch and Bound (B&B) algorithm called, the Branch, Bound, and Remember (BB&R) algorithm, which uses the Distributed Best First Search (DBFS) exploration strategy for solving the 1|r (i) |at (i) scheduling problem, a single machine scheduling problem where the objective is to find a schedule with the minimum total tardiness. Memory-based dominance strategies are incorporated into the BB&R algorithm. In addition, a modified memory-based dynamic programming algorithm is also introduced to efficiently compute lower bounds for the 1 vertical bar r (i) vertical bar at (i) scheduling problem. Computational results are reported, which shows that the BB&R algorithm with the DBFS exploration strategy outperforms the best known algorithms reported in the literature.
We study the classical multi-item capacitated lot-sizing problem with hard capacities. There are N items, each of which has specified sequence of demands over a finite planning horizon of discrete T periods;the demand...
详细信息
ISBN:
(纸本)9783540727910
We study the classical multi-item capacitated lot-sizing problem with hard capacities. There are N items, each of which has specified sequence of demands over a finite planning horizon of discrete T periods;the demands are known in advance but can vary from period to period. All demands must be satisfied on time. Each order incurs a time-dependent fixed ordering cost regardless of the combination of items or the number of units ordered, but the total number of units ordered cannot exceed a given capacity C. On the other hand, carrying inventory from period to period incurs holding costs. The goal is to find a feasible solution with minimum overall ordering and holding costs. We show that the problem is strongly NP-Hard, and then propose a novel facility location type LP relaxation that is based on an exponentially large subset of the well-known flow-cover inequalities;the proposed LP can be solved to optimality in polynomial time via an efficient separation procedure for this subset of inequalities. Moreover, the optimal solution of the LP can be rounded to a feasible integer solution with cost that is at most twice the optimal cost;this provides a 2-Approximation algorithm, being the first constant approximation algorithm for the problem. We also describe an interesting on-the-fly variant of the algorithm that does not require to solve the LP a-priori with all the flow-cover inequalities. As a by-product we obtain the first theoretical proof regarding the strength of flow-cover inequalities in capacitated inventory models. We believe that some of the novel algorithmic ideas proposed in this paper have a promising potential in constructing strong LP relaxations and LP-based approximation algorithms for other inventory models, and for the capacitated facility location problem.
暂无评论