Search

In this work we address the problem of determining the optimal types of products and their quantities that should be loaded on a fleet of heterogeneous one or two level trucks so that the weighted sum of delivered products is maximized, with the weights being an exponential function of the lateness computed for each unit shipped. We propose a mixed integer linear formulation followed by a two-phase solution approach. During phase one the formulation is solved aiming at maximizing the weighted sum of products delivered, whereas for the second phase, the formulation is solved aiming at minimizing the number of trucks, while ensuring that the objective function attained in phase one is not compromised. A greedy heuristic is also proposed in order to better quantify the advantages of adopting the proposed exact approach with respect to solution quality. To assess the performance of the proposed approach we used two sets of test instances, a large set of randomly generated instances that resemble the practical application that motivated this research, and a small set of real instances provided by the company. The results of our computational experiments suggest that the proposed exact solution approach is very effective in solving realistic sized instances.

The storage location assignment problem (SLAP), also known as the slotting problem involves the decisions of how much and where should be stored each stock keeping unit (SKU) in the fast-pick area with the aim to minimize total order-picking and replenishment costs associated to the distance traveled by the picking operators. Motivated by this, we propose to analyze the impact of SKUs demand correlation on the slotting decisions. Based on an experimental design, the effects of SKUs with correlated demand are analyzed. Results show that the most significant factor with respect to the total distance traveled is the number of orders, followed by the capacity of the bins and the number of bins in each location. Results of an instance solved to optimality by a commercial solver and a greedy heuristic in which the latter does not consider the demand correlation illustrate the impact that demand correlation has on the solution obtained.

17 páginas nly a few studies in the available scientific literature address the problem of having a group of workers that do not share identical levels of productivity during the planning horizon. This study considers a workforce scheduling problem in which the actual processing time is a function of the scheduling sequence to represent the decline in workers’ performance, evaluating two classical performance measures separately: makespan and maximum tardiness. Several mathematical models are compared with each other to highlight the advantages of each approach. The mathematical models are tested with randomly generated instances available from a public e-library.

The p-regions is a mixed integer programming (MIP) model for the exhaustive clustering of a set of n geographic areas into p spatially contiguous regions while minimizing measures of intraregional heterogeneity. This is an NP-hard problem that requires a constant research of strategies to increase the size of instances that can be solved using exact optimization techniques. In this article, we explore the benefits of an iterative process that begins by solving the relaxed version of the p-regions that removes the constraints that guarantee the spatial contiguity of the regions. Then, additional constraints are incorporated iteratively to solve spatial discontinuities in the regions. In particular we explore the relationship between the level of spatial autocorrelation of the aggregation variable and the benefits obtained from this iterative process. The results show that high levels of spatial autocorrelation reduce computational times because the spatial patterns tend to create spatially contiguous regions. However, we found that the greatest benefits are obtained in two situations: (1) when n/p≥3; and (2) when the parameter p is close to the number of clusters in the spatial pattern of the aggregation variable.

The obsolescence and related energy inefficiency of many industrial processes are currently an obstacle in the transition toward a more sustainable manufacturing sector. The objective of this work is to exploit the advantages of technology updating for improving the economic and environmental performance of the cement industry. To this end, we have developed a mathematical approach to optimize technological updating decisions of existing cement supply chains. Our approach is based on a multiobjective mixed-integer linear programming formulation that determines whether technological updating projects should be undertaken at a given manufacturing stage, such that both environmental and financial goals are best met. A test instance based on a cement supply chain is solved to illustrate how significant benefits can be attained by applying our systematic approach.

This research introduces the multi-product capacitated facility location problem with general production and building costs (MP-CFLPGC). The MP-CFLPGC extends previous problems found in the literature by including multiple products and general production and building cost functions that allow the modeling of different behaviors like economies of scale and congestion. The MP-CFLPGC is formulated as a mixed integer linear program (MILP). To evaluate the performance of the proposed formulation we analyze the results of a commercial optimizer on a set of 288 randomly generated test instances that resemble the Colombian cement industry supply chain. After one hour the optimizer achieved an optimality gap of 1.0 % or less in 55 % out of the 288 test instances. On average the optimality gap was 3.57 %. Additionally, we propose a randomized mathematical-programming-based heuristic for the test instances where the MILP formulation presents significantly high optimality gaps.

While the cement industry is perceived as one of the major contributors to climate change, with a 7 % share of total C O 2 emissions, direct taxes on emissions of these gases have been little applied to this productive sector. The present study addresses the issue of assessing the effectiveness of carbon taxation methods in encouraging sustainable cement production processes. In particular, the effect of different carbon emission prices on decisions that lead to a reduction of C O 2 emissions in a representative cement supply chain, was studied. A mixed-integer linear formulation is used to describe a non-taxed base case against a case that explicitly includes carbon taxes. Computational experiments conducted on a realistic-sized instance built based on publicly available data from the cement sector, showed that environmental benefits can be attained after implementing a carbon taxation mechanism. The results indicate that with a rate between 15 US $ and 150 US $ by C O 2 emitted ton over a predefined cap, will drive cleaner cement production scenarios with a reduction of emissions up to 24 % , respect to a non-taxed scenario used as the base line. The proposed decision-making tool can be effectively used by any cement company that needs to better assess the trade-off between its financial objectives and the sustainability goal of carbon emissions reduction.

A scheduling problem commonly observed in the metal working industry has been studied in this research effort. A job shop equipped with one batch processing machine (BPM) and several unit-capacity machines has been considered. Given a set of jobs, their process routes, processing requirements, and size, the objective is to schedule the jobs such that the makespan is minimized. The BPM can process a batch of jobs as long as its capacity is not exceeded. The batch processing time is equal to the longest processing job in the batch. If no batches were to be formed, the scheduling problem under study reduces to the classical job shop problem with makespan objective, which is known to be nondeterministic polynomial time-hard. A network representation of the problem using disjunctive and conjunctive arcs, and a simulated annealing (SA) algorithm are proposed to solve the problem. The solution quality and run time of SA are compared with CPLEX, a commercial solver used to solve the mathematical formulation and with four dispatching rules. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using SA to solve large-scale problems.

This paper considers the problem of scheduling a set of jobs subject to arbitrary release dates and sequence-dependent setup times on a single machine with the objective of minimizing the maximum completion of all the jobs, or makespan. This problem is often found in manufacturing processes such as painting and metalworking. A new mixed integer linear program (MILP) is firstly proposed. Because the problem is known to be NP-hard, a beam search heuristic is developed. Computational experiments are carried out using a well-known set of instances from the literature. Our results show that the proposed heuristic is effective in finding high quality solutions at low computational cost. A novel mixed integer linear program is proposed for the scheduling problem.Experiments showed that a commercial solver can only solve small instances.A beam search (BS) heuristic is proposed to solve larger instances.Experiments showed that the BS heuristic finds high quality solutions at low cost.

Given a set of jobs and two batch processing machines (BPMs) arranged in a flow shop environment, the objective is to batch the jobs and sequence the batches such that the makespan is minimized. The job sizes, ready times, and processing times on the two BPMs are known. The batch processing machines can process a batch of jobs as long as the total size of all the jobs assigned to a batch does not exceed its capacity. Once the jobs are batched, the processing time of the batch on the first machine is equal to the longest processing job in the batch; processing time of the batch on the second machine is equal to the sum of processing times of all the jobs in the batch. The batches cannot wait between two machines (i.e., no-wait). The problem under study is NP-hard. We propose a mathematical formulation and present a particle swarm optimization (PSO) algorithm. The solution quality and run time of PSO is compared with a commercial solver used to solve the mathematical formulation. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using PSO to solve large-scale problems.

This research is motivated by our interactions with an electronics manufacturer who assembles and tests printed circuit boards (PCBs) used in consumer products. Environmental stress screening (ESS) chambers are commonly used to test PCBs to detect early failures before they are used in the field. The chambers are capable of testing multiple PCBs simultaneously (i.e., batch processing machines). The minimum testing time of each PCB and their size are known. The objective is to group these PCBs into batches and schedule the batches formed on ESS chambers such that the makespan is minimized. The ESS chambers can process a batch of jobs as long as its capacity is not violated. Each ESS chamber is unique with respect to its capacity. The problem is NP-hard. Consequently, a particle swarm optimization (PSO) algorithm is proposed. The effectiveness of the PSO algorithm is evaluated by comparing its results to a random-key genetic algorithm and a commercial solver used to solve a mixed-integer linear program. A thorough experimental study conducted indicates that the PSO algorithm reports better quality solution in a short time on larger problem instances.

This research aims at minimizing the makespan of a set of identical batch processing machines arranged in parallel. Each job is defined by its processing time, ready time, and size. Each machine can process several jobs simultaneously as long as the machine capacity is not exceeded. The batch processing and ready times depend upon the batch composition. The batch processing time is equal to the longest processing job in the batch, and the batch ready time is equal to the largest ready time among those jobs in the batch. The problem under study is NP-hard. Consequently, a constructive heuristic is proposed and its performance with respect to solution quality and computational cost is compared against other solution approaches found in the literature. The computational experiments on a set of randomly generated instances show that the performance of the proposed heuristic is competitive with respect to solution quality and requires little computational cost.

In this paper we consider the problem of scheduling a set of identical batch processing machines arranged in parallel. A Greedy Randomized Adaptive Search Procedure (GRASP) approach is proposed to minimize the makespan under the assumption of non-zero job ready times, arbitrary job sizes and arbitrary processing times. Each machine can process simultaneously several jobs as a batch as long as the machine capacity is not violated. The batch processing time is equal to the largest processing time among those jobs in the batch. Similarly, the batch ready time is equal to the largest ready time among those jobs in the batch. The performance of the proposed GRASP approach was evaluated by comparing its results to a lower bound and heuristics published in the literature. Experimental study suggests that the solution obtained from the GRASP approach is superior compared to other heuristics.

This paper considers a two-stage flow shop scheduling problem with a batch processing machine (BPM) in each stage. The processing time of the batch on the first machine is equal to the longest processing job in the batch, and the batch processing time on the second machine is equal to the sum of processing times of all the jobs in the batch. The jobs cannot wait between the two stages. The problem under study with the makespan objective is NP-hard. An ant colony optimisation (ACO) algorithm combined with batch forming and local search heuristics is proposed and its solution is compared with: a particle swarm optimisation (PSO) algorithm; a greedy randomised adaptive search procedure (GRASP) algorithm; and a commercial solver used to solve the mixed-integer linear formulation. The experimental study helps to highlight the advantages, in terms of solution quality and run time, of using ACO to solve large-scale problems.

In a flow shop with two batch processing machines (BPMs) one of the key objectives is to minimise the makespan. In this study jobs with different sizes were batched together, without exceeding the machine capacity, and processed in the BPMs. Job ready times were also taken into consideration hence, a batch cannot be started unless all the jobs in the batch are ready and available. Also, the batches cannot wait between two machines (i.e., no-wait). The problem under study is NP-hard. A greedy randomised adaptive search procedure (GRASP) algorithm has been developed for this problem. Experiments were conducted to study up to 200 job instances. The solution quality of the GRASP algorithm was compared with the results of a mathematical model developed using CPLEX and a particle swarm optimisation algorithm. The experimental study highlights the advantages, in terms of solution quality of using GRASP to solve large-scale problems.

This paper aims to minimise the makespan of a set of identical batch processing machines in parallel. The batch processing machine can process a batch of jobs as long as the total size of all the jobs in the batch does not exceed its capacity. The processing time of the job and its size are given. Batch processing time is equal to the longest processing job in the batch. Two interdependent decisions are required, namely grouping jobs into batches, and scheduling the batches on the machines. The problem under study is NP-hard and hence a Genetic Algorithm (GA) approach is proposed. The effectiveness of the GA approach to solve randomly generated problems was compared with a Simulated Annealing (SA) approach, a Random Keys Genetic Algorithm (RKGA), a Hybrid Genetic Heuristic (HGH) and a commercial solver. The proposed GA approach was found to be very effective in finding a good solution in a short time as opposed to SA, RKGA and a commercial solver. Both GA and HGH are marginally better than each other on different problem instances. [Submitted 17 August 2007; Revised 10 October 2007; Revised 30 May 2008; Revised 29 July 2008; Accepted 15 September 2008]