The Monden Problem, also known as the Output Rate Variation Problem, is one of the original formulations for mixed-model assembly line-level scheduling problems in a just-in-time system. In this paper, we develop a new branch-and-bound procedure for the problem that uses several new and previously proposed lower and upper bounds. The algorithm also includes several dominance rules that leverage the symmetry in the problem as well as a new labelling procedure that avoids repeated exploration of previously examined partial solutions. The branching strategy exploits the capabilities of current multiprocessor computers by exploring the search tree in a parallel fashion. The algorithm has been tested on several sets of instances from the literature and is able to optimally solve problems that are double the size of those addressed by other procedures previously reported in the literature.

The assembly line balancing problem is a classical optimisation problem whose objective is to assign each production task to one of the stations on the assembly line so that the total efficiency of the line is maximized. This study proposes a novel hybrid method to solve the simple version of the problem in which the number of stations is fixed, a problem known as SALBP-2. The hybrid differs from previous approaches by encoding individuals of a genetic algorithm as instances of a modified problem that contains only a subset of the solutions to the original formulation. These individuals are decoded to feasible solutions of the original problem during fitness evaluation in which the resolution of the modified problem is conducted using a dynamic programming based approach that uses new bounds to reduce its state space. Computational experiments show the efficiency of the method as it is able to obtain several new best-known solutions for some of the benchmark instances used in the literature for comparison purposes.

Test assembly design problems appear in the areas of psychology and education, among others. The goal of these problems is to construct one or multiple tests to evaluate the test subject. This paper studies a recent formulation of the problem known as the one-dimensional minimax bin-packing problem with bin size constraints (MINIMAX_BSC). In the MINIMAX_BSC, items are initially divided into groups and multiple tests need to be constructed using a single item from each group, while minimizing differences among the tests. We first show that the problem is NP-Hard, which remained an open question. Second, we propose three different local search neighborhoods derived from the exact resolution of special cases of the problem, and combine them into a variable neighborhood search (VNS) metaheuristic, Finally, we test the proposed algorithm using real-life-based instances. The results show that the algorithm is able to obtain optimal or near-optimal solutions for instances with up to 60000-item pools. Consequently, the algorithm is a viable option to design large-scale tests, as well as to provide tests for online small-sized situations such as those found in e-learning platforms. (C) 2015 Elsevier Ltd. All rights reserved.Preprin

This work addresses a particular case of the group shop scheduling problem (GSSP) which will be denoted as the fixed group shop scheduling problem (FGSSP). In a FGSSP, job operations are divided into stages and each stage has a set of machines associated to it which are not shared with the other stages. All jobs go through all the stages in a specific order, where the operations of the job at each stage need to be finished before the job advances to the following stage, but operations within a stage can be performed in any order. This setting is common in companies such as leaf spring manufacturers and other automotive companies. To solve the problem, we propose a novel heuristic procedure that combines a decomposition approach with a constraint programming (CP) solver and a restart mechanism both to avoid local optima and to diversify the search. The performance of our approach was tested on instances derived from other scheduling problems that the FGSSP subsumes, considering both the cases with and without anticipatory sequence-dependent setup times. The results of the proposed algorithm are compared with off-the-shelf CP and mixed integer linear programming (MILP) methods as well as with the lower bounds derived from the study of the problem. The experiments show that the proposed heuristic algorithm outperforms the other methods, specially on large-size instances with improvements of over 10% on average.