A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints

This paper presents a heuristic, which concentrates on solving a large-scale static dial-a-ride problem bearing complex constraints. In this heuristic, a properly organized local search strategy and a diversification strategy are used to improve initial solutions. Then the improved solutions can be refined further by an intensification strategy. The performance of this heuristic was evaluated by intensive computational tests on some randomly generated instances. Small gaps to the lower bounds from the column generation method were obtained in very short time for instances with no more than 200 requests. Although the result is not sensitive to the initial solution, the computational time can be greatly reduced if some effort is spent to construct a good initial solution. With this good initial solution, larger instances up to 2000 requests were solved in less than 10 hours on a popular personal computer.     

Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line

A monolithic and a hierarchical approach are presented for balancing and scheduling of a flexible assembly line (FAL). The system is made up of a set of assembly stations in series, each with limited work space and is capable of simultaneously producing a mix of product types. The objective is to determine an assignment of assembly tasks to stations and an assembly schedule for all products so as to complete the products in minimum time. In the monolithic approach balancing and scheduling decisions are made simultaneously. In the hierarchical approach, however, first the station workloads are balanced, and then detailed assembly schedule is determined for prefixed task assignments and assembly routes by solving a permutation flowshop problem. Mixed integer programming formulations are presented for the two approaches. Numerical examples are included to illustrate and compare the approaches and some computational results are reported.     

An integrated cutting stock and sequencing problem

In this paper an integrated problem formulated as an integer linear programming problem is presented to find an optimal solution to the cutting stock problem under particular pattern sequencing constraints. The solution uses a Lagrangian approach. The dual problem is solved using a modified subgradient method. A heuristic for the integrated problem is also presented. The computational results obtained from a set of unidimensional instances that use these procedures are reported.     

The stochastic U-line balancing problem: A heuristic procedure

Many heuristics have been proposed for the assembly line balancing problem due to its computational complexity and difficulty in identifying an optimal solution. Still, the basic line balancing model fails to consider a number of realistic elements. The implementation of a Just-In-Time manufacturing system generally entails the replacement of traditional straight assembly lines with U-shaped lines. An important issue in the U-line balancing problem is the consideration of task time variability due to human factors or various disruptions. In this paper, we consider the stochastic U-line balancing problem. A hybrid heuristic is presented consisting of an initial feasible solution module and a solution improvement module. To gain insight into its performance, we analyze the heuristic under different scenarios of task time variability. Computational results clearly demonstrate the efficiency and robustness of our algorithm.     

A heuristic approach for combined equipment-planning and routing in multi-layer SDH/WDM networks

The paper deals with a multi-layer network design problem for a high-speed telecommunication network based on Synchronous Digital Hierarchy (SDH) and Wavelength Division Multiplex (WDM) technology. The network has to carry a certain set of demands with the objective of minimizing the investment in the equipment. The different layers are the fiber-layer, 2.5 Gbit/s-, 10 Gbit/s- and WDM-systems. Several variations of the problem including path-protected demands and specific types of cross-connect equipment are considered. The problem is described as a mixed integer linear programming model and some results for small networks are presented. Two greedy heuristics, a random start heuristic and a GRASP-like approach are implemented to solve large real world problems.     

GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem

We propose a GRASP using an hybrid heuristic-subproblem optimization approach for the Multi-Level Capacitated Minimum Spanning Tree (MLCMST) problem. The motivation behind such approach is that to evaluate moves rearranging the configuration of a subset of nodes may require to solve a smaller-sized MLCMST instance. We thus use heuristic rules to define, in both the construction and the local search phases, subproblems which are in turn solved exactly by employing an integer programming model. We report numerical results obtained on benchmark instances from the literature, showing the approach to be competitive in terms of solution quality. The proposed GRASP have in fact improved the best known upper bounds for almost all of the considered instances.     

A goal programming approach to simple U-line balancing problem

In this paper, a goal programming model for the simple U-line balancing (ULB) problem is developed. The model is based on the integer programming formulation developed by Urban [Urban, Note: Optimal balancing of U-shaped assembly lines, Management Science 44(5) (1998) 738–741] for the ULB problem and the goal model of Deckro and Rangachari [Deckro, Rangachari, A goal approach to assembly line balancing, Computers and Operations Research 17 (1990) 509–521] developed for the traditional single model assembly line balancing (ALB) problem. The proposed model which is the first multi-criteria decision making approach to the U-line version provides increased flexibility to the decision maker since several conflicting goals can be simultaneously considered.     

A chance-constrained approach to stochastic line balancing problem

In this paper, chance-constrained 0–1 integer programming models for the stochastic traditional and U-type line balancing (ULB) problem are developed. These models are solved for several test problems that are well known in the literature and the computational results are given. In addition, a goal programming approach is presented in order to increase the system reliability, which is arising from the stochastic case.     

一种高压开关产品的装配过程优化问题研究

本文针对高压开关产品的装配线提出一个实际的装配过程优化问题:高压开关产品的装配过程优化问题。该问题是在传统的空间布局问题中,加入了装配线工艺流程约束,是一类新的优化问题。本文为该问题建立了整数规划模型,并为该模型开发了启发式算法。然后以ZF11-252产品的装配过程为例,采用启发式算法求解模型。     

A fast meta-heuristic approach for the $$(\alpha ,\beta )-k$$-feature set problem

The feature selection problem aims to choose a subset of a given set of features that best represents the whole in a particular aspect, preserving the original semantics of the variables on the given samples and classes. In 2004, a new approach to perform feature selection was proposed. It was based on a NP-complete combinatorial optimisation problem called (\(\alpha ,\beta \))-k-feature set problem. Although effective for many practical cases, which made the approach an important feature selection tool, the only existing solution method, proposed on the original paper, was found not to work well for several instances. Our work aims to cover this gap found on the literature, quickly obtaining high quality solutions for the instances that existing approach can not solve. This work proposes a heuristic based on the greedy randomised adaptive search procedure and tabu search to address this problem; and benchmark instances to evaluate its performance. The computational results show that our method can obtain high quality solutions for both real and the proposed artificial instances and requires only a fraction of the computational resources required by the state of the art exact and heuristic approaches which use mixed integer programming models.     

A new formulation and an exact approach for the many-to-many hub location-routing problem

An important problem of the freight industry is the parcel delivery network design, where several facilities are responsible for assembling flows from several origins, re-routing them to other facilities where the flows are disassembled and the packages delivered to their final destinations. In order to provide this service, local tours are established for the vehicles assigned to each of the processing facilities, which are then responsible for the pickup and delivery tasks. This application gives rise to the many-to-many hub location routing problem that is the combination of two well known problems: the vehicle routing problem and the single assignment hub location problem. In this work, a new formulation for this important problem is proposed and solved by a specially tailored Benders decomposition algorithm. The proposed method is robust enough to solve instances up to 100 nodes having 4 million integer variables.     

A variable neighborhood search based matheuristic for nurse rostering problems

A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various requirements. A matheuristic approach is introduced, based on a set of neighborhoods iteratively searched by a commercial integer programming solver within a defined global time limit, relying on a starting solution generated by the solver running on the general integer programming formulation of the problem. Generally speaking, a matheuristic algorithm is a heuristic algorithm that uses non trivial optimization and mathematical programming tools to explore the solutions space with the aim of analyzing large scale neighborhoods. Randomly generated instances, based on the considered nurse rostering problem, were solved and solutions computed by the proposed procedure are compared to the solutions achieved by pure solvers within the same time limit. The results show that the proposed solution approach outperforms the solvers in terms of solution quality. The proposed approach has also been tested on the well known Nurse Rostering Competition instances where several new best results were reached.     

Absalom: Balancing assembly lines with assignment restrictions

Assembly line balancing problems (ALBPs) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing products among the work stations along the line. On the one hand, research has focussed on developing effective and fast solution methods for exactly solving the simple assembly line balancing problem (SALBP). On the other hand, a number of real-world extensions of SALBP have been introduced but solved with straight-forward and simple heuristics in many cases. Therefore, there is a lack of procedures for exactly solving such generalized ALBP.In this paper, we show how to extend the well-known solution procedure Salome [Scholl, A., Klein, R., 1997. Salome: A bidirectional branch-and-bound procedure for assembly line balancing. Informs J. Comput. 9 319–334], which is able to solve even large SALBP instances in a very effective manner, to a problem extension with different types of assignment restrictions (called ARALBP). The extended procedure, referred to as Absalom, employs a favorable branching scheme, an arsenal of bounding rules and a variety of logical tests using ideas from constraint programming.Computational experiments show that Absalom is a very promising exact solution approach although the additional assignment restrictions complicate the problem considerably and necessitate a relaxation of some components of Salome.     

Simple heuristics for the assembly line worker assignment and balancing problem

We propose simple heuristics for the assembly line worker assignment and balancing problem. This problem typically occurs in assembly lines in sheltered work centers for the disabled. Different from the well-known simple assembly line balancing problem, the task execution times vary according to the assigned worker. We develop a constructive heuristic framework based on task and worker priority rules defining the order in which the tasks and workers should be assigned to the workstations. We present a number of such rules and compare their performance across three possible uses: as a stand-alone method, as an initial solution generator for meta-heuristics, and as a decoder for a hybrid genetic algorithm. Our results show that the heuristics are fast, they obtain good results as a stand-alone method and are efficient when used as a initial solution generator or as a solution decoder within more elaborate approaches.     

A branch-and-bound algorithm to minimize the line length of a two-sided assembly line

A new branch-and-bound algorithm is presented to solve the two-sided assembly line balancing problem of type 1 (TALB-1). First, a pair of two directly facing station is defined as a position, and then the two-sided assembly line (TAL) is relaxed to a one-sided assembly line (OAL). Some new lower bound on positions are computed, and dominance rules and reduction rules for the one-sided assembly line balancing problem of type 1 (OALB-1) are extended and incorporated into a station-oriented assignment procedure for the TALB-1 problem. Finally, the tests are carried out on a well-known benchmark set of problem instances, and experimental results demonstrate that the proposed procedure is efficient.     

Robust support vector machines for multiple instance learning

This paper presents the multiple instance classification problem that can be used for drug and molecular activity prediction, text categorization, image annotation, and object recognition. In order to model a more robust representation of outliers, hard margin loss formulations that minimize the number of misclassified instances are proposed. Although the problem is $\mathcal{NP}$ -hard, computational studies show that medium sized problems can be solved to optimality in reasonable time using integer programming and constraint programming formulations. A three-phase heuristic algorithm is proposed for larger problems. Furthermore, different loss functions such as hinge loss, ramp loss, and hard margin loss are empirically compared in the context of multiple instance classification. The proposed heuristic and robust support vector machines with hard margin loss demonstrate superior generalization performance compared to other approaches for multiple instance learning.     

Binary fuzzy goal programming approach to single model straight and U-shaped assembly line balancing

Assembly line balancing generally requires a set of acceptable solutions to the several conflicting objectives. In this study, a binary fuzzy goal programming approach is applied to assembly line balancing. Models for balancing straight and U-shaped assembly lines with fuzzy goals (the number of workstations and cycle time goals) are proposed. The binary fuzzy goal programming models are solved using the methodology introduced by Chang [Chang, C.T., 2007. Binary fuzzy goal programming. European Journal of Operational Research 180 (1), 29–37]. An illustrative example is presented to demonstrate the validity of the proposed models and to compare the performance of straight and U-shaped line configurations.     

An Integer Multicommodity Flow Model Applied to the Rerostering of Nurse Schedules

The problem of rerostering service schedules is very common in organizations that work shifts around the clock every day of the year with a set number of employees. Whenever one or more workers announce that they will not be able to attend to tasks previously assigned in their schedule, those tasks must be performed at the expense of alterations in the schedules of other workers. These changes should not conflict with the rules laid down by the administration and employment contracts and should affect the previous schedules as little as possible. This is a difficult real problem calling for a computational tool to cope with it easily. In the paper the issue is described in detail in the context of nurse scheduling and formulated as an integer multicommodity flow problem with additional constraints, in a multi-level acyclical network. A heuristic was implemented as a first approach to solving the problem. Subsequently the integer linear programming formulation of the multicommodity flow model and two linear relaxations were tested using CPLEX [2] optimizers. The computational results reported regard real instances from a Lisbon state hospital. Satisfactory rosters were obtained within acceptable computational times in all instances tested, either with the integer optimizer, or with the heuristic. This being so, refinements will be undertaken to embed these methodologies in a decision support system that may assist the head nurse in her daily rerostering activities.     

A Lagrangian relaxation approach to the mixed-product assembly line sequencing problem: A case study of a door-lock company in Taiwan

In mixed-product assembly line sequencing, the production resources required for the assembly lines should be scheduled to minimize the overall cost and meet customer demand. In this paper, we study an assembly line sequencing problem for the door-lock industry in Taiwan and develop an integer programming formulation with realistic constraints. The complex solution space makes the resulting program difficult to solve using commercial optimization packages. Therefore, a heuristic based on the Lagrangian relaxation principle is developed to solve this problem efficiently. We evaluate the efficiency of the developed Lagrangian relaxation heuristic by comparing its solutions with those obtained using a commercial optimization package: the computational results show that the developed heuristic solves the real-world problem faster than the optimization package by almost 15 times in CPU time at a comparable solution quality.     

Balancing stochastic two-sided assembly lines: A chance-constrained,piecewise-linear,mixed integer program and a simulated annealing algorithm

Two-sided assembly lines are often designed to produce large-sized products, such as automobiles, trucks and buses. In this type of a production line, both left-side and right-side of the line are used in parallel. In all studies on two-sided assembly lines, the task times are assumed to be deterministic. However, in real life applications, especially in manual assembly lines, the tasks may have varying execution times defined as a probability distribution. The task time variation may result from machine breakdowns, loss of motivation, lack of training, non-qualified operators, complex tasks, environment, etc. In this paper, the problem of balancing two-sided assembly lines with stochastic task times (STALBP) is considered. A chance-constrained, piecewise-linear, mixed integer program (CPMIP) is proposed to model and solve the problem. As a solution approach a simulated annealing (SA) algorithm is proposed. To assess the effectiveness of CPMIP and SA algorithm, a set of test problems are solved. Finally, computational results indicating the effectiveness of CPMIP and SA algorithm are reported.