Among the different tasks in production logistics, job scheduling is one of the most important at the operational decision-making level to enable organizations to achieve competiveness. Scheduling consists in the allocation of limited resources to activities over time in order to achieve one or more optimization objectives. Flow-shop (FS) scheduling problems encompass the sequencing processes in environments in which the activities or operations are performed in a serial flow. This type of configuration includes assembly lines and the chemical, electronic, food, and metallurgical industries, among others. Scheduling has been mostly investigated for the deterministic cases, in which all parameters are known in advance and do not vary over time. Nevertheless, in real-world situations, events are frequently subject to uncertainties that can affect the decision-making process. Thus, it is important to study scheduling and sequencing activities under uncertainties since they can cause infeasibilities and disturbances. The purpose of this paper is to provide a general overview of the FS scheduling problem under uncertainties and its role in production logistics and to draw up opportunities for further research. To this end, 100 papers about FS and flexible flow-shop scheduling problems published from 2001 to October 2016 were analyzed and classified. Trends in the reviewed literature are presented and finally some research opportunities in the field are proposed.
In this paper, we introduce a unified mathematical formulation for the Capacitated Vehicle Routing Problem (CVRP) and for the Capacitated Location Routing Problem (CLRP), adopting radiality constraints in order to guarantee valid routes and eliminate subtours. This idea is inspired by formulations already employed in electric power distribution networks, which requires a radial topology in its operation. The results show that the proposed formulation greatly improves the convergence of the solver.
This paper tackles an extension to the Multi-activity Combined Timetabling and Crew Scheduling Problem (MCTCSP). The goal of the original problem is to schedule the minimum number of homogenous workers required, in order to visit a set of customers characterized by services needed against schedule availability. However, since in home services it is common to have specialized workers, a mathematical model considering a heterogeneous workforce is proposed. As a solution, a GRASP-based algorithm is designed. In order to test the metaheuristic performance, 110 instances from the literature are adapted to include categorical skills. In addition, another 10 instances are randomly generated to consider large problems. The results show that the proposed GRASP finds optimal solutions in 46% of the cases and saves 40–96% computational time.
This paper presents the implementation of an efficient modified genetic algorithm for solving the multi-traveling salesman problem (mTSP). The main characteristics of the method are the construction of an initial population of high quality and the implementation of several local search operators which are important in the efficient and effective exploration of promising regions of the solution space. Due to the combinatorial complexity of mTSP, the proposed methodology is especially applicable for real-world problems. The proposed algorithm was tested on a set of six benchmark instances, which have from 76 and 1002 cities to be visited. In all cases, the best known solution was improved. The results are also compared with other existing solutions procedure in the literature.
This paper presents a multiobjective ant colony algorithm for the Multi-Depot Vehicle Routing Problem with Backhauls (MDVRPB) where three objectives of traveled distance, traveling times and total consumption of energy are minimized. An ant colony algorithm is proposed to solve the MDVRPB. The solution scheme allows one to find a set of ordered solutions in Pareto fronts by considering the concept of dominance. The effectiveness of the proposed approach is examined by considering a set of instances adapted from the literature. The computational results show high quality results within short computing times.
This paper addresses the scheduling problem in a Permutation Flow Shop (PFS) environment, which is associated with many types of industries such as chemical, petrochemical, automobile manufacturing, metallurgical, textile, etc. Thus, this work intends to solve a PFS scheduling problem in order to minimize the total weighted tardiness, since it is an important sequencing criterion not only for on time delivery jobs but also for customer satisfaction. To solve the problem, GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic is proposed as a solution, which has shown competitive results compared with other combinatorial problems. In addition, two utility functions called Weighted Modified Due Date (WMDD) and Apparent Tardiness Cost (ATC) are proposed to develop GRASP. These are based on dynamic dispatching rules and also known for solving the problem of total weighted tardiness for single machine scheduling problem. Next, an experimental design was carried out for comparing the GRASP performance with both utility functions and against the WEDD dispatching rule results. The results indicate that GRASP-WMDD could improve the total weighted tardiness in 47.8% compared with WEDD results. Finally, the GRASP-WMDD performance for the PFS total tardiness problem was evaluated, obtaining a relative deviation index of 13.89% and ranking the method over 26 heuristics and metaheuristics.
This paper presents the problem of redesigning a supply network of large scale by considering variability of the demand. The central problematic takes root in determining strategic decisions of closing and adjusting of capacity of some network echelons and the tactical decisions concerning to the distribution channels used for transporting products. We have formulated a deterministic Mixed Integer Linear Programming Model (MILP) and a stochastic MILP model (SMILP) whose objective functions are the maximization of the EBITDA (Earnings before Interest, Taxes, Depreciation and Amortization). The decisions of Network Design on stochastic model as capacities, number of warehouses in operation, material and product flows between echelons, are determined in a single stage by defining an objective function that penalizes unsatisfied demand and surplus of demand due to demand changes. The solution strategy adopted for the stochastic model is a scheme denominated as Sample Average Approximation (SAA). The model is based on the case of a Colombian company dedicated to production and marketing of foodstuffs and supplies for the bakery industry. The results show that the proposed methodology was a solid reference for decision support regarding to the supply networks redesign by considering the expected economic contribution of products and variability of the demand.
This paper considers a multi-objective version of the Multiple Traveling Salesman Problem (MOmTSP). In particular, two objectives are considered: the minimization of the total traveled distance and the balance of the working times of the traveling salesmen. The problem is formulated as an integer multi-objective optimization model. A non-dominated sorting genetic algorithm (NSGA-II) is proposed to solve the MOmTSP. The solution scheme allows one to find a set of ordered solutions in Pareto fronts by considering the concept of dominance. Tests on real world instances and instances adapted from the literature show the effectiveness of the proposed algorithm.