Search

Fil: Blanco, Aníbal M. Universidad Nacional del Sur - CONICET. Planta Piloto de Ingeniería Química - PLAPIQUI. Bahia Blanca, Argentina. Fil: Moreno, Susana M. Universidad Nacional del Sur - CONICET. Planta Piloto de Ingeniería Química - PLAPIQUI. Bahia Blanca, Argentina. Fil: Taraborelli, Carolina. Universidad Nacional del Sur - CONICET. Planta Piloto de Ingeniería Química - PLAPIQUI. Bahia Blanca, Argentina. Fil: D´Angelo, Flavio. Universidad Nacional de Río Negro, CIT Río Negro. Río Negro, Argentina. Fil: Iturmendi, Facundo. Universidad Nacional de Río Negro, CIT Río Negro. Río Negro, Argentina. Fil: Bandoni, Alberto J. Universidad Nacional del Sur - CONICET. Planta Piloto de Ingeniería Química - PLAPIQUI. Bahia Blanca, Argentina. Fil: D´Angelo, Flavio. Jugos S.A., Parque Industrial. Río Negro, Argentina. Fil: Iturmendi, Facundo. Jugos S.A., Parque Industrial. Río Negro, Argentina. We describe the development of a decision-support tool to assist in the operations of a large concentrated apple and pear juice plant. The tool?s objective is to generate detailed schedules of clarified juice batches to be produced in the following weeks considering incoming fruit forecasts, commercial commitments, and infrastructural constraints. The tool is based on two interactive modules, PLANNER and SIMOPT, with different and complementary purposes. Each module is based on mixed-integer models with specific inputs, outputs, and user interfaces. PLANNER consists of three submodules: (i) planning assigns a batch of concentrated juice to be produced on a specific day, taking into account cleaning activities, rest days, raw material availability, and production and storage constraints; (ii) preprocessing organizes juice orders in batches; and (iii) pooling provides a detailed monitoring of semielaborated juice in storage pools in terms of inventories and sugar and acid content. Finally, SIMOPT provides a detailed optimal operative condition of the plant together with a thorough calculation of specific costs. This information is used by PLANNER to evaluate the corresponding economic objective functions. Besides providing optimal target conditions to the plant and feasible production schedules, the developed tools generate production guidelines in the long term and allow performing scenario studies. Describimos el desarrollo de una herramienta de apoyo a la decisión para ayudar en las operaciones de una gran planta concentrada de jugo de manzana y pera. El objetivo de la herramienta es generar cronogramas detallados de lotes de jugo clarificados que se producirán en las próximas semanas considerando los pronósticos de fruta entrantes, los compromisos comerciales y las restricciones de infraestructura. La herramienta se basa en dos módulos interactivos, PLANNER y SIMOPT, con propósitos diferentes y complementarios. Cada módulo se basa en modelos enteros mixtos con entradas, salidas e interfaces de usuario específicas. PLANNER consta de tres submódulos: (i) la planificación asigna un lote de jugo concentrado para ser producido en un día específico, teniendo en cuenta las actividades de limpieza, los días de descanso, la disponibilidad de materia prima y las limitaciones de producción y almacenamiento; (ii) el preprocesamiento organiza los pedidos de jugo en lotes; y (iii) la agrupación proporciona un monitoreo detallado del jugo semielaborado en las piscinas de almacenamiento en términos de inventarios y contenido de azúcar y ácido. Finalmente, SIMOPT proporciona una condición operativa óptima detallada de la planta junto con un cálculo exhaustivo de los costos específicos. PLANNER utiliza esta información para evaluar las funciones de objetivos económicos correspondientes. Además de proporcionar condiciones óptimas para la planta y programas de producción factibles, las herramientas desarrolladas generan pautas de producción a largo plazo y permiten realizar estudios de escenarios.

In this paper, we focus on the problem of optimizing deadline violations for executing tasks in various heterogeneous computational environments. To address the problem, we formulated it as a binary nonlinear programming (BNP) model, which maximize the number of completed tasks and optimize the resource utilization of servers. To solve the BNP model in a polynomial complexity, we propose a heuristic task scheduling method, which iteratively schedules a task to the first core such that the accumulated slack time of all scheduled tasks is minimum, until the core cannot finish any task, and executes tasks with the earliest deadline first in each core to execute as many task as possible in a core. Experiment results based on a real world trace show that our method has upto 100% less task violations, and has the best performance in resource efficiency optimization in overall, compared with eight classical and state-of-the-art heuristic methods.

Purpose: This research develops a batch scheduling model for a three-stage flow shop with job processors in the first and second stages and a batch processor in the third stage. The model integrates production process activities and a product inspection activity to minimize the expected total actual flow time. Design/methodology/approach: The problem of batch scheduling for a three-stage flow shop is formulated as a mathematical model, and a heuristic algorithm is proposed to solve the problem. This model applies backward scheduling to accommodate the objective of minimizing the expected total actual flow time. Findings: This research has proposed a batch scheduling model for a three-stage flow shop with job and batch processors to produce multiple items and an algorithm to solve the model. The objective is to minimize total actual time. The resulting production batches can be sequenced between all types of products to minimize idle time, and the batch processor capacity affects the sample size and indirectly affects the production batch size. Originality/value: This research develops a batch scheduling model for a three-stage flow shop constituting job and batch processors and carrying out integrated production and inspection activities to minimize the expected total actual flow time

This study is inspired by a batch scheduling problem in metal working industry which guarantees to satisfy a due date as a commitment to customers. Actual flowtime adopts the backward scheduling approach and considers the due date. Using the actual flowtime as the objective means that the solution is oriented to satisfy the due date, and simultaneosly to minimize the length of time of the parts spending in the shop. This research is to address a problem of scheduling batches consisting of multiple items of parts processed on a batch processor where the completed parts must be delivered several time at different due dates. We propose an algorithm to solve the problem.

In this paper, we address a model for supply chain coordination. There are m manufacturers modelled as single machines, each of which processes a specific set of jobs (products). After processing is completed, jobs are batched, and batches are shipped to a customer by means of vehicles. The problem consists in concurrently finding a production schedule of the jobs, a partition of jobs into delivery batches and an assignment of delivery batches to vehicles, so that jobs are delivered within their deadlines and total costs are minimised. We focus on a scenario characterised by fixed departure times and inventory holding costs. For each departure time there is a given number of vehicles, possibly having limited capacity. Each job incurs a cost proportional to the time from job completion to delivery departure. In this paper, we show that the problem is NP-hard even for a very restricted case, and report various polynomiality results for two scenarios, namely: (i) when the production sequence of each manufact...

We considered the online scheduling problem of simple linear deteriorating job families on m parallel batch machines to minimize the makespan, where the batch capacity is unbounded. In this paper, simple linear deteriorating jobs mean that the actual processing time p j of job J j is assumed to be a linear function of its starting time s j , i.e., p j = &alpha, j s j , where &alpha, j &gt, 0 is the deterioration rate. Job families mean that one job must belong to some job family, and jobs of different families cannot be processed in the same batch. When m = 1 , we provide the best possible online algorithm with the competitive ratio of ( 1 + &alpha, max ) f , where f is the number of job families and &alpha, max is the maximum deterioration rate of all jobs. When m &ge, 1 and m = f , we provide the best possible online algorithm with the competitive ratio of 1 + &alpha, max .

In this study, a batch scheduling with job grouping and batch sequencing is considered. A clustering algorithm and dispatching rule selection model is developed to minimize total tardiness. The model and algorithm are based on the constrained k-means algorithm and neural network. We also develop a method to generate a training dataset from historical data to train the neural network. We use numerical examples to demonstrate that the proposed algorithm and model efficiently and effectively solve batch scheduling problems.

Inland waterways form a natural network infrastructure with capacity for more traffic. Transportation by ship is widely promoted as it is a reliable, efficient and environmental friendly way of transport. Nevertheless, locks managing the water level on waterways and within harbors sometimes constitute bottlenecks for transportation over water. The lockmaster's problem concerns the optimal strategy for operating such a lock. In the lockmaster's problem we are given a lock, a set of upstream-bound ships and another set of ships traveling in the opposite direction. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper, a dynamic programming algorithm is proposed that solves the lockmaster's problem in polynomial time. This algorithm can also be used to solve a single batching machine scheduling problem more efficiently than the current algorithms from the literature do. We extend the algorithm such that it can be applied in realistic settings, taking into account capacity, ship-dependent handling times, weights and water usage. In addition, we compare the performance of this new exact algorithm with the performance of some (straightforward) heuristics in a computational study.

This paper addresses a batch scheduling problem for a three-stage hybrid flowshop consisting of a machining stage processing common and unique components on unrelated parallel machines, an assembly stage combining the components into assembled products with complex assembly structures, and a differentiation stage processing the assembled products on dedicated machines to produce different product types. The common components are the same for all products and are processed in batches, while the unique components are dedicated to respective given product types and are processed individually (one-by-one component). The goal is to schedule all the products with different assembly structures to minimize total actual flow time (TAFT) defined as total time interval of components to be processed from their arrival times to their common due date. A non-linear programming model is proposed, where small size problems can be solved optimally using the LINGO software, and large size problems is to be solved using a heuristic algorithm. The proposed algorithm consists of two sub-algorithms. The first one is constructed using a shortest processing time (SPT) based heuristic to get a job sequence as an initial solution and the second one is to improve the initial solution using the variable neighbourhood descent (VND) method with neighbourhood insert and swap move operators. In solving the problem with the algorithm, two scenarios arise, e.g., the same and the different sequences for all stages. A set of hypothetical data is generated for different hierarchical assembly structures to test the model and the algorithm, and the results show that the different sequences for all stages obtain solutions with better performances than the same ones.

In this paper, a novel pattern-based method is developed for the generation of optimal schedules for energy-integrated batch process systems. The proposed methodology is based on the analysis of available schedules for the identification of repetitive patterns. It is shown that optimal schedules of energy-integrated batch processes are composed of several repeating sections (or building blocks), and their sizes and relative positions are dependent on the scheduling horizon and constraints. Based on such a decomposition, the proposed pattern-based algorithm generates an optimal schedule by computing the number and sequence of these blocks. The framework is then integrated with rigorous optimization-based approach wherein it is shown that the learning from the pattern-based solution significantly improves the performance of rigorous optimization. The main advantage of the pattern-based method is the significant reduction in computational time required to solve large scheduling problems, thus enabling the possibility of on-line rescheduling. Three literature examples were considered to demonstrate the presence of repeating patterns in optimal schedules of energy-integrated batch systems. The effectiveness of the proposed methodology was illustrated using an integrated reactor-separator system.

Purpose: Today’s manufacturing facilities are challenged by highly customized products and just in time manufacturing and delivery of these products. In this study, a batch scheduling problem has been addressed to enable on-time completion of customer orders in a lean manufacturing environment. The problem is optimizing the partitioning of product components into batches and scheduling of the resulting batches where each customer order is received as a set of products made of various components. Design/methodology/approach: Three different mathematical models for minimization of total earliness and tardiness of customer orders are developed to provide on-time completion of customer orders and also, to avoid excess final product inventory. The first model is a non-linear integer programming model whereas the second is a linearized version of the first. Finally, to solve larger sized instances of the problem, an alternative linear integer model is presented. Findings: Computational study using a suit set of test instances showed that the alternative linear integer model is able to solve all test instances in varying sizes within quite shorter computer times compared to the other two models. It has also been showed that the alternative model is able to solve moderate sized real-world problems. Originality/value: The problem under study differentiates from existing batch scheduling problems in the literature owing to the inclusion of new circumstances that are present in real-world applications. Those are: customer orders consisting of multi-products made of multi-parts, processing of all parts of the same product from different orders in the same batch, and delivering the orders only when all related products are completed. This research also contributes to the literature of batch scheduling problem by presenting new optimization models.

International audience; A collection of intersecting sets of operations is considered. These sets of operations are performed successively. The operations of each set are activated simultaneously. Operation durations can be modified. The cost of each operation decreases with the increase in operation duration. In contrast, the additional expenses for each set of operations are proportional to its time. The problem of selecting the durations of all operations that minimize the total cost under constraint on completion time for the whole collection of operation sets is studied. The mathematical model and method to solve this problem are presented. The proposed method is based on a combination of Lagrangian relaxation and dynamic programming. The results of numerical experiments that illustrate the performance of the proposed method are presented. This approach was used for optimization multi-spindle machines and machining lines, but the problem is common in engineering optimization and thus the techniques developed could be useful for other applications.

In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP-complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan.

This research addresses a batch scheduling model for a single-machine under a Just-In-Time (JIT) production system that produces discrete parts. The objective is to minimize the total actual flow time, defined as the time when parts are flowing on the shop floor from its arrival time to their common delivery time. The decision variables are the number of batches, integer batch sizes, and the sequence of the resulting batches. The problem is solved based on the Lagrange Relaxation method. The optimality test of the proposed algorithm is done by comparing the result of the proposed algorithm with the Integer Composition method. The result of numerical experiments demonstrates that the proposed algorithm is very efficient to solve the problems.

This paper addresses an integrated production and delivery batch scheduling problem for a make-to-order environment over daily time period, where the holding costs of in-process and completed parts at a supplier location and of completed parts at a manufacturer location are distinguished. All orders of parts with different due dates from the manufacturer arrive at the same time. The parts are produced in production batches and subsequently the completed parts are delivered in delivery batches using a capacitated vehicle in order to be received at the respective due dates. This study was aimed at finding an integrated schedule of production and delivery batches so as to meet the due date at minimum total cost consisting of the corresponding holding cost and delivery cost. The holding cost is a derivation of the so-called actual flow time (AFT), while the delivery cost is assumed to be proportional to the number of deliveries. The problems can be formulated as an integer non-linear programming model, and the global optimal solution can be obtained using optimization software. A heuristic algorithm is proposed to cope with the computational time problem using software. The numerical experiences show that the proposed algorithm yields near global optimal solutions.

We study a special two-stage flexible flowshop, which consists of several parallel identical machines in the first stage and a single machine in the second stage. We assume identical jobs, and the option of batching, with a required setup time prior to the processing of a new batch. We also consider the option to use only a subset of the available machines. The objective is minimum makespan. A unique optimal solution is introduced, containing the optimal number of machines to be used, the sequence of batch sizes, and the batch schedule. The running time of our proposed solution algorithm is independent of the number of jobs, and linear in the number of machines

An S-stage hybrid (or flexible) flow shop, with sequence-independent uniform set-up times, parallel batching machines with compatible parallel batch families (like in casting or heat treatments in furnaces, chemical or galvanic baths, painting in autoclave, etc.) has been analysed with the purpose of reducing the number of tardy jobs (and the makespan); in Graham’s notation: FPB(m1, m2, …, mS)|p-batch, . Jobs are sorted dynamically (at each new delivery); batches are closed within sliding (or rolling) time windows and processed in parallel by multiple identical machines. Computation experiments have shown the better performance on benchmarks of the two proposed heuristics based on new formulations of the critical ratio (CRsetup) considering the ratio of allowance set-up and processing time in the scheduling horizon, which improves the weighted modified operation due date rule.

International audience; With the increasing energy price, the rapid growth of electricity demand and severe challenges for sustainable development, energy-efficient scheduling is becoming more and more important for power-intensive manufacturing industry, especially for batch production companies. This paper investigates a bi-objective single machine batch scheduling problem with non-identical job sizes, the time-of-use (TOU) electricity prices, and different energy consumption rates of the machine. The first objective is to minimize the makespan and the second is to minimize the total energy costs, by considering both the machine utilization and the economic cost. The problem is formulated as an integer programming model. Then, an exact ε-constraint method is adapted to obtain the exact Pareto front. To deal with large scale problems, based on decomposition ideas, two heuristic methods are developed to obtain approximate Pareto fronts. Computational experiments on randomly generated instances show the effectiveness of the methods. A study case of a real-world glass manufacturing company is also conducted to show that the proposed methods are promising for practical usages.

International audience; Time-of-use (TOU) electricity pricing has been a common practice to enhance the peak load regulation capability of power grid. Meanwhile, it provides a good opportunity for industries to reduce energy costs, especially for energy-intensive ones, where batch scheduling is often involved. Majority of batch scheduling problems have been proved to be NP-hard, even for most single-machine environments. Optimizing batch scheduling under TOU policy in these industries will be of great significance. Single-machine batch scheduling is an important basis for more complicated shop scheduling problems. This paper investigates a bi-objective single-machine batch scheduling problem under TOU policy: the first objective is to minimize the makespan and the second is to minimize the total electricity costs. The considered problem is first formulated as a bi-objective mix-integer linear programming (MILP) model and is demonstrated to be NP-hard. Subsequently, the MILP is simplified by analyzing properties and search space for a Pareto optimal solution is greatly reduced. Then, an exact ϵ-constraint method is adapted to obtain its Pareto front, which is accelerated due to these properties. Finally, a preferable solution is recommended for decision makers via a fuzzy-logic-based approach. Computational results on randomly generated instances show the effectiveness of the proposed approach.

International audience; The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature.

Article history: Received 10 March 2010 Received in revised form July, 25, 2011 Accepted 26 July 2011 Available online 27 July 2011 This paper presents a mathematical model for the problem of minimizing the maximum lateness on a single machine when the deteriorated jobs are delivered to each customer in various size batches. In reality, this issue may happen within a supply chain in which delivering goods to customers entails cost. Under such situation, keeping completed jobs to deliver in batches may result in reducing delivery costs. In literature review of batch scheduling, minimizing the maximum lateness is known as NP-Hard problem; therefore the present issue aiming at minimizing the costs of delivering, in addition to the aforementioned objective function, remains an NP-Hard problem. In order to solve the proposed model, a Simulation annealing meta-heuristic is used, where the parameters are calibrated by Taguchi approach and the results are compared to the global optimal values generated by Lingo 10 software. Furthermore, in order to check the efficiency of proposed method to solve larger scales of problem, a lower bound is generated. The results are also analyzed based on the effective factors of the problem. Computational study validates the efficiency and the accuracy of the presented model. © 2012 Growing Science Ltd. All rights reserved

We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on m parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines m=2 or m=3, respectively. When m≥4, we present an online algorithm with a competitive ratio of 1.5+o(1).

Cataloged from PDF version of article. In this paper, we address a single-machine scheduling problem with due dates and batch setup times to minimize the weighted number of tardy jobs. We give a pseudo-polynomial dynamic program and a fully-polynomial approximation scheme for the case where the due dates are uniform within a family. 2007 Elsevier Ltd. All rights reserved.

This paper discusses the integration model of batch production and preventive maintenance scheduling on a single machine producing an item to be delivered at a common due date. The machine is a deteriorating machine that requires preventive maintenance to ensure the availability of the machine at a desired service level. Decision variables of the model are the number of preventive maintenances, the schedule, length of production runs, as well as the number of batches, batch sizes and the production schedule of the resulting batches for each production run. The objective function of the model is to minimize the total cost consisting of inventory costs during parts processing, setup cost and cost of preventive maintenance. The results show three important points: First, the sequence of optimal batches always follows the SPT (short processing time). Second, variation of preventive maintenance unit cost does not influence the sequence of batches. Third, the first production run length from production starting time is smaller than the next production run length and this pattern continues until the due date. When in process inventory unit cost is increased, the pattern will continue until a specified cost limit, and beyond the limit the pattern will change to be the opposite pattern.

In the aircraft industry structural components, referred to as part numbers (PN), have to be subject to an heat treatment in capacitated burn-in furnaces for a pre-defined period (exposure time) in order to provide them with specific physic and chemical features (e.g. hardness, corrosion resistance, conductivity). Two or more part numbers can be grouped in a batch and treated simultaneously in the same furnace if it is possible to individuate a common exposure time. In order to minimize the total completion time (makespan) of the process it needs to determine the appropriate grouping of the part numbers into batches (batching problem) to be processed by each furnace (scheduling problem). The problem can be modeled as a batch scheduling problem on parallel machines where the batching and the scheduling problem are considered at the same time. Starting from a real case study, we present an original integer linear programming formulation in the case of two capacitated parallel machines and we provide the results obtained on two real instances coming from the aircraft industry.

International audience; The issue of energy has emerged as one of the greatest challenges facing mankind. In an industrial perspective, the development of site utility systems (generally combined heat and power (CHP) systems) for the generation and management of utilities provides a great potential source for energy savings. However, in most industrial sites, a master-slave relationship usually governs this kind of system and limits the potential operating capacity of CHP. To improve the decision-making process, Agha et al. (2010. Integrated production and utility system approach for optimising industrial unit operation. Energy, 35, 611-627) have proposed an integrated approach that carries out simultaneous and consistent scheduling of batch production plants and site utility systems. The modelling of the problem relies on a mixed integer linear programming (MILP) formulation. Nevertheless, although it is a powerful mathematical tool, it still remains difficult to use for non-expert engineers. In this framework, a graphical formalism based on existing representations (STN, RTN) has been developed: the extended resource task network (ERTN). Combined with an efficient and generic MILP formulation, it permits various kinds of industrial problems, including production and consumption of utility flows to be modelled homogenously. This paper focuses on the semantic elements of the ERTN formalism and illustrates their use through representative examples.

This paper addresses a cutting stock problem under typical resource constraints that arise when working centres with nesting capabilities are associated with automatic feeders/stackers. The critical resource is the number of buffers available to host the batches built up by the centre. To cope with it, pattern and batch sequencing problems must be addressed simultaneously. A tabu-search algorithm exploring batch output sequences is proposed. The algorithm never opens more stacks than buffers, respects batch compatibility/precedence constraints, and keeps the maximum order spread under control. To demonstrate its effectiveness and efficiency, a computational study was set up, solving 920 test problems derived from the literature. The study enabled a proper tuning of the method and offered encouraging results: in 228 cases an optimum was found; in nearly all, the gap from the optimum was below 1%. Computation times range from fractions of seconds to a couple of minutes in the worst cases. Compared to existing methods, the algorithm provides on average the same solution quality, with the advantage of solving a problem which is more general and hence closer to application. The paper includes a discussion on the method extensions required to deal with asynchronous stacking and heterogeneous batches.

International audience; In this paper, we deal with the problem of minimizing the makespan of washing operations in hospitals sterilization services. After use in operating blocs, reusable medical devices (RMD) are sent to the sterilization service which is composed of various processes. In the washing step, different sets of RMD, used for different operations, may be washed together without exceeding washer capacity. An RMD set must be washed in one cycle and so, we are not allowed to split RMD sets. In this case, we consider a batch scheduling problem where RMD sets may have different sizes and different release dates for washing. Note that if all release dates are equal, the problem is reduced to a bin packing problem. We provide a mixed integer linear programming model which aims at minimizing the makespan of washing operations. We provide and also experiment some heuristics based on classical bin packing algorithms.

Journal of Combinatorial Optimization, 17 (3), ISSN:1382-6905, ISSN:1573-2886