Transmission system expansion planning by a branch-and-bound algorithm

A branch and bound (B&B) algorithm using the DC model, to solve the power system transmission expansion planning by incorporating the electrical losses in network modelling problem is presented. This is a mixed integer nonlinear programming (MINLP) problem, and in this approach, the so-called fathoming tests in the B&B algorithm were redefined and a nonlinear programming (NLP) problem is solved in each node of the B&B tree, using an interior-point method. Pseudocosts were used to manage the development of the B&B tree and to decrease its size and the processing time. There is no guarantee of convergence towards global optimisation for the MINLP problem. However, preliminary tests show that the algorithm easily converges towards the best-known solutions or to the optimal solutions for all the tested systems neglecting the electrical losses. When the electrical losses are taken into account, the solution obtained using the Garver system is better than the best one known in the literature.     

Machine scheduling in the presence of sequence-dependent setup times and a rate-modifying activity

Rate modifying activity (RM) is a type of maintenance after which the processing rate of the machine increases. RM is a very new topic in academic studies. However, it is very common in real world situations. In this paper, we study the integrated problem of assigning a common due-date to all jobs, scheduling the jobs and making decisions about the position of RM in a single machine environment in which the setup times are sequence dependent. The objective is minimising the summation of earliness costs, tardiness costs and due date related costs. This problem has never been studied in the literature with any arbitrary criterion. We construct a time-dependent travelling salesman problem (TDTSP) formulation for this problem. The position of the optimal common due date and some dominance properties for the position of RM are presented. A branch and bound (B&B) procedure is developed to solve the problem optimally. Numerical results justify the effectiveness of the B&B method for small problems. For larger problems, two robust metaheuristics are proposed.     

The coordinated production and transportation scheduling problem with a time-sensitive product: a branch-and-cut algorithm

In many supply chain scenarios in which short lifespan products are considered, production and transportation decisions must be made in a coordinated manner with no inventory stage. Hence, a solution to this problem conveys information about production starting times of each product lot at facility and delivery times of the lots to various customer-sites located in different geographic regions. In this paper, we study a variant of the problem that single product with limited shelf life is produced at single facility. Once produced, production lot is directly distributed to the customers with non-ignorable transportation time by single vehicle having limited capacity before the lifespan. Objective is to determine the minimum time required to produce and deliver all customer demands. To this end, we develop a branch-and-cut (B&C) algorithm using several valid inequalities adopted from the existing literature to improve lower bounds and applying a local search based on simulated annealing approach to improve upper bounds. On test problems available in the literature, we evaluate the performance of the B&C algorithm. Results show the promising performance of the B&C algorithm.     

A novel branch-and-bound algorithm for the chance-constrained resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) has been widely studied during the last few decades. In real-world projects, however, not all information is known in advance and uncertainty is an inevitable part of these projects. The chance-constrained resource-constrained project scheduling problem (CC-RCPSP) has been recently introduced to deal with uncertainty in the RCPSP. In this paper, we propose a branch-and-bound (B&B) algorithm and a mixed integer linear programming (MILP) formulation that solve a sample average approximation of the CC-RCPSP. We introduce two different branching schemes and eight different priority rules for the proposed B&B algorithm. The computational results suggest that the proposed B&B procedure clearly outperforms both a proposed MILP formulation and a branch-and-cut algorithm from the literature.     

Solving an apparel trim placement problem using a maximum cover problem approach

A trim placement problem from the apparel industry is presented and solved. The problem is related to cutting and packing problems, which have received attention in the literature for close to 40 years. The problem is motivated by a pants layout problem involving irregularly-shaped pieces. A two-stage strategy is commonly employed, with large pieces, or panels, arranged first, followed by smaller pieces, or trim. This paper assumes the panels have been arranged, and presents an approach for placing the trim pieces into unused “containers” of the stock material. Groups of trim pieces are first generated using existing polygon containment algorithms. Then, groups are assigned to containers to maximize a weighted function of the trim pieces. The mathematical programming formulation is developed, which is a generalization of the Maximum Cover Problem, a well-known problem in the location literature. Due to wide variability in branch and bound solution times, a Lagrangian Heuristic incorporating an improvement heuristic is developed. Computational experience demonstrates the effectiveness of the Lagrangian Heuristic on real pants markers. The optimal solution is found for all, and solution times are less than branch and bound in 10 out of 12 problem instances (considerably less in three), and only slightly more in the other two. Times are also less variable than branch and bound, an important characteristic with an interactive layout system.     

Optimal material release times in stochastic production environments

The problem of determining the 'optimal' material release times is an important and complex problem for most manufacturing firms. In this age of global competition, firms need to have low inventories, short cycle times and the ability to meet customer orders on time. In this paper, we consider a firm operating in a Make-To-Order environment and formulate this problem as an unconstrained cost minimization problem for a fixed sequence of work. We propose a solution methodology using stochastic approximation and infinitesimal perturbation analysis of a transient state simulation of the system. We discuss the implementation of this algorithm and present some preliminary results. We also present an algorithm to obtain a lower bound on the optimal objective function value under certain conditions.     

Economic Lot Scheduling for Two-Product Problem

In this paper we propose an algorithm for the two-product single machine Economic Lot Scheduling Problem (ELSP). Past research on this problem has relied heavily on the assumption that both products are produced cyclically. In particular Boctor's algorithm provides optimal solution to the two-product problem under such assumption. We first simplify Boctor's algorithm and then propose an algorithm which allows for the unequal cycle time for the more frequently manufactured product. We show that the cost corresponding to our solution is either less than 1.015 times the cost obtained from the Independent Solution, which is a lower bound of the optimal solution, or is better than that obtained by Boctor's algorithm. An example is used to show that the difference in cost can be as much as 24%.     

Balancing Multi-Manned Assembly Lines With Walking Workers: Problem Definition,Mathematical Formulation,and an Electromagnetic Field Optimisation Algorithm

Assembly lines are widely used in industrial environments that produce standardised products in high volumes. Multi-manned assembly line is a special version of them that allows simultaneous operation of more than one worker at the same workstation. These lines are widely used in large-sized product manufacturing since they have many advantages over the simple one. This article has dealt with multi-manned assembly line balancing problem with walking workers for minimising the number of workers and workstations as the first and second objectives, respectively. A linear mixed-integer programming formulation of the problem has been firstly addressed after the problem definition is given. Besides that, a metaheuristic based on electromagnetic field optimisation algorithm has been improved. In addition to the classical electromagnetic field optimisation algorithm, a regeneration strategy has been applied to enhance diversification. A particle swarm optimisation algorithm from assembly line balancing literature has been modified to compare with the proposed algorithm. A group of test instances from many precedence diagrams were generated for evaluating the performances of all solution methods. Deviations from lower bound values of the number of workers/workstations and the number of optimal solutions obtained by these methods are concerned as performance criteria. The results obtained by the proposed programming formulations have been also compared with the solutions obtained by the traditional mathematical model of the multi-manned assembly line. Through the experimental results, the performance of the metaheuristic has been found very satisfactory according to the number of obtained optimal solutions and deviations from lower bound values.     

Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements

Home health care or home care (HHC/HC) refers to the delivery of social, medical and paramedical services to clients in their own homes. Each day, care workers start from the HHC/HC centre, visit some clients and return to the centre. During the service delivery process, there is usually a lunch break for each worker. In this paper, we address a real-life home care worker scheduling and routing problem with the consideration of lunch break requirements. A three-index mathematical model is constructed for the problem. The problem is decomposed into a master problem and several pricing sub-problems, and is optimally solved by a branch-and-price (B&P) algorithm. Specifically, a sophisticated label-correcting algorithm is designed to address lunch break constraints in pricing sub-problems; some cutting-edge acceleration strategies are applied during the column generation process. Experimental results show that the proposed B&P algorithm is able to produce satisfied solutions within an acceptable runtime and outperforms the mixed integer programming solver CPLEX.     

A heuristic for assigning facilities to locations to minimize WIP travel distance in a linear facility

Many manufacturing systems require an assignment of machines to locations along a straight track, so as to optimize material flow. This paper uses a cut approach to the corresponding quadratic assignment problem, and derives a heuristic which generates a good solution. In addition, a modified lower bound to the assignment problem is also developed, which is always better than the classical lower bound. Results showing the performance of the heuristic are demonstrated, along with a comparison of the modified and classical lower bound. In almost all the test problems, the solution generated by the heuristic was either optimal or better than any solution obtained by other methods. Extension of the heuristic to more general cases also is considered.     

用边界元方法和复合形法求解三维结构的下限安定载荷

基于安定分析的静力定理,建立了用常规边界元方法进行三维理想弹塑性结构安定分析的整套求解算法。下限安定分析所需的弹性应力场直接由边界元方法求出,所需的自平衡应力场由一组带有待定系数的自平衡应力场基矢量的线性组合进行模拟,这些自平衡应力场基矢量通过边界元弹塑性迭代计算获取。安定分析问题最终被归结为一系列未知变量较少的非线性数学规划子问题并通过复合形法直接求解。计算结果表明了算法的有效性。     

Single-item production–delivery scheduling problem with stage-dependent inventory costs and due-date considerations

This paper studies an integrated scheduling problem for a single-item, make-to-order supply chain system consisting of one supplier, one capacitated transporter and one customer. Specifically, we assume the existence in the production stage of an intermediate inventory that works as a buffer to balance the production rate and the transportation speed. Jobs are first processed on a single machine in the production stage, and then delivered to the pre-specified customer by a capacitated vehicle in the delivery stage. Each job has a due date specified by the customer, and must be delivered to the customer before its due date. Moreover, it is assumed that a job that is finished before its departure date or arrives at the customer before its due date will incur a stage-dependent corresponding inventory cost (WIP inventory, finished-good inventory or customer inventory cost). The objective is to find a coordinated production and delivery schedule such that the sum of setup, delivery and inventory costs is minimised. We formulate the problem as a nonlinear model in a general way and provide some properties. We then derive a precise instance from the general model and develop a heuristic algorithm for solving this precise instance. In order to evaluate the performance of the heuristic algorithm, we propose a simple branch-and-bound (B&B) approach for small-size problems, and a lower bound based on the Lagrangian relaxation method for large-size problems. Computational experiments show that the heuristic algorithm performs well on randomly generated problems.     

A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows

A branch and bound algorithm is described for optimal cyclic scheduling in a robotic cell with processing time windows. The objective is to minimise the cycle time by determining the exact processing time on each machine which is limited within a time window. The problem is formulated as a set of prohibited intervals of the cycle time, which is usually applied in the robotic cyclic scheduling problem with fixed processing times. Since both bounds of these prohibited intervals are linear expressions of the processing times, we divide these prohibited intervals into a series of the subsets and transform the problem into enumerating the non-prohibited intervals of cycle time in each subset. This enumeration procedure is completed by an efficient branch and bound algorithm, which could find an optimal solution by enumerating partial non-prohibited intervals. Computational results on the benchmark instances and randomly generated test instances indicate that the algorithm is effective.     

Balancing manual mixed-model assembly lines using overtime work in a demand variation environment

This study deals with the balancing problem of a manual mixed-model assembly line, where the production volume or the product mix changes from shift to shift during the planning horizon. The unstable demand can be characterised by several representative scenarios, and the line uses overtime work to meet the demand variation. The balancing problem concerns how to assign assembly tasks to stations and determine the amount of overtime in each possible demand scenario. The objective is to satisfy the demand in each possible scenario with the minimum labour costs paid for both normal shifts and overtime work. A lower bound on the labour costs is proposed, and a heuristic algorithm is developed to quickly find a feasible solution. A branch, bound and remember (BB&;R) algorithm is then proposed to find better solutions. These solution methods are tested on 765 instances. The BB&;R algorithm obtains optimal solutions for 510 instances and gives high-quality solutions for the remaining 255 instances within 60?s. The experimental results show that the use of overtime work and adjustable cycle times significantly reduces the labour costs, especially when the demand or task processing time variations are large.     

Applying simulated annealing to the open shop scheduling problem

This paper addresses the problem of scheduling a nonpreemptive open shop with the objective of minimizing makespan. A neighborhood search algorithm based on the simulated annealing technique is proposed. The algorithm is tested on randomly generated problems, benchmark problems in the literature, and new hard problems generated in this paper. Computational results show that the algorithm performs well on all of the test problems. In many cases, an optimum solution is found, and in others the distance from the optimum or lower bound is quite small. Moreover, some of the benchmark problems in the literature are solved to optimality for the first time.     

Daily scheduling of caregivers with stochastic times

This paper addresses a daily caregiver scheduling and routing problem arising in home health care or home care service providers. The problem is quite challenging due to its uncertainties in terms of travel and service times derived from changes in road traffic conditions and customer health status in practice. We first model the problem as a stochastic programme with recourse, where the recourse action is to skip customers without services if the caregiver arrives later than their latest starting service time (i.e. hard time window requirements). Then, we formulate the problem as a set partitioning model and solve it with a branch-and-price (B&P) algorithm. Specifically, we devise an effective discrete approximation method to calculate the arrival time distribution of caregivers, incorporate it into a problem-specific label algorithm, and use a removal-and-insertion-based heuristic and the decremental state-space relaxation technique to accelerate the pricing process. Finally, we conduct numerical experiments on randomly generated instances to validate the effectiveness of the discrete approximation method and the proposed B&P algorithm.     

Single machine scheduling problem with batch setups involving positional deterioration effects and multiple rate-modifying activities

This article considers a single machine scheduling problem with batch setups, positional deterioration effects, and multiple optional rate-modifying activities to minimize the total completion time. This problem is formulated as an integer quadratic programming problem. In view of the complexity of optimally solving this problem, a two-phase heuristic algorithm is proposed where an optimal but non-integer solution is obtained in the first phase by solving a continuous relaxed version of the problem. This solution serves as a lower bound for the optimal value of the total completion time. The second phase of the algorithm generates an integer solution using a simple rounding scheme that is optimum or very close to optimum for this problem. Empirical evaluation and comparison with an existing heuristic algorithm show that the proposed heuristic algorithm is substantially more effective in solving large-size problem instances.     

Capacity-constrained reorder intervals for materials requirements planning systems

This paper develops a model for the reorder interval problem for general production systems with constant demand, multiple capacity constraints, commonality, non-instantaneous production, and non-nested reorder intervals. We present this model in the context of a materials requirements planning (MRP) system.

Four simple greedy heuristics are presented to find solutions to the model. A six-factor experiment with 192 test problems is used to evaluate the heuristics. The factors in the experiment included the procedures, number of items, capacity tightness, degree of commonality, setup cost to carrying cost ratio, and setup time to run time ratio. For smaller problems the heuristics are compared with optimal solutions found with an exact branch-and-bound algorithm. For larger problems, the heuristics are compared with a lower bound.

The results of the experiment show that the heuristics provide excellent solutions across all experimental factors. Computing times for the proposed heuristics appear to be practical even for realistic MRP environments with many thousands of items.     

A Branch-and-Bound Algorithm for Flow Shop Scheduling Problems

This article is concerned with the solution of the flow shop scheduling problem in which all jobs have the same machine ordering. A branch-and-bound algorithm is developed for finding the sequence of J jobs to be processed on M machines which minimizes the schedule time. Thib algorithm consists of branching and bounding processes, but without the backtracking process which guarantees optimality. The procedure employed is that in constructing a subset of feasible sequences, a node representing a partial sequence is branched. Selection of the node depends on the lower-bound concept as a decision rule. This lower bound is based on resolving the conflict of jobs on the last machine. By using this algorithm, the number of explored nodes is considerably reduced and, hence, the computational effort involved in obtaining an optimal or near-optimal solution is decreased. High quality of solutions is obtained. Computationally, this algorithm extends the size of problems that can reasonably be solved.     

Spread time considerations in operational fixed job scheduling

In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.