Optimal scheduling of the -machine assembly-type flow shop
Optimal scheduling of the 3-machine assembly-type flow shop
We address the 3-Machine Assembly-Type Flowshop Scheduling Problem (3MAF). This problem is known to be NP-complete in the strong sense. We propose an exact branch and bound method based on a recursive enumeration of potential inputs and outputs of the machines. Using this algorithm, several large size instances have been solved to optimality.
Optimal tool partitioning rules for numerically controlled punch press operations
Ordres médians et ordres de Slater des tournois
Dans cet article, nous essayons de faire le point sur les résultats concernant les aspects combinatoires et algorithmiques des ordres médians et des ordres de Slater des tournois. La plupart des résultats recensés sont tirés de différentes publications ; plusieurs sont originaux.
Parametric integer programming
Polynomial time algorithms for special open shop problems with precedence constraints and unit processing times
Polynomially solvable traveling salesman problems
Remarks on pebble games on graphs
Résolution d'un problème d'ordonnancement cyclique à itérations indépendantes et contraintes de ressources
Small-Dimensional Linear Programming and Convex Hulls Made Easy.
The disjoint cliques problem
The partial inverse minimum cut problem with L1-norm is strongly NP-hard
The partial inverse minimum cut problem is to minimally modify the capacities of a digraph such that there exists a minimum cut with respect to the new capacities that contains all arcs of a prespecified set. Orlin showed that the problem is strongly NP-hard if the amount of modification is measured by the weighted L1-norm. We prove that the problem remains hard for the unweighted case and show that the NP-hardness proof of Yang [RAIRO-Oper. Res.35 (2001) 117–126] for this problem with additional bound...
The random linear bottleneck assignment problem
Three easy special cases of the euclidean travelling salesman problem
Вычислительная сложность выигрывающих стратегий в полиномиальных играх двух лиц