An Efficient Approach for the Reentrant Parallel Machines Scheduling Problem under Consumable Resources Constraints

An Efficient Approach for the Reentrant Parallel Machines Scheduling Problem under Consumable Resources Constraints

Fayçal Belkaid (Manufacturing Engineering Laboratory of Tlemcen (MELT), University of Tlemcen, Tlemcen, Algeria & LGIPM, University of Lorraine, Metz, France), Farouk Yalaoui (ICD -LOSI, University of Technology of Troyes, Troyes, France) and Zaki Sari (Manufacturing Engineering Laboratory of Tlemcen (MELT), University of Tlemcen, Tlemcen, Algeria)
DOI: 10.4018/IJISSCM.2016070101
OnDemand PDF Download:
No Current Special Offers


In present manufacturing environment, the reentrant scheduling problem is one of the most important issues in the planning and operation of production systems. It has a large scope such as capacity distribution and inventory control. On the other hand, the markets are very competitive; it is a critical requirement of operational management to have effective management of resources (consumable and renewable) so as to achieve optimal production plan. This study considers a reentrant parallel machines scheduling problem with consumable resources. Each job consumes several components and must be processed more than once in a stage composed of identical parallel machines. The resources availability, jobs assignment and sequencing at each cycle and are considered and optimized simultaneously. On the basis of this representation, a MILP model is developed. Thus, that MILP model can be used for the problem in order to find the exact solution. Since, this problem is clearly NP-hard, and optimal solutions for large instances are highly intractable, a genetic algorithm is developed to obtain near-optimal solution. Then, an improvement phase based on different local search procedures are performed and examined to generate better solutions. The system performances are assessed in terms of measures such as the solution quality and the execution time. The effectiveness of the proposed metaheuristic is examined based on comparative study. The simulation results demonstrate that the presented algorithm is able to find an optimal solution for small-sized problems and can effectively find a near optimal solution for large-sized problems to minimize the makespan of the considered problem.
Article Preview

1. Introduction

The scheduling problem is one of the most frequently occurring operational problems in manufacturing; it aims to organize jobs over time on certain resources (Baker, 1974). The objective of scheduling is to optimize different criteria of production systems such as makespan. The scheduling field has paid increasing attention in recent years and attracts the interest of both academics and industrial researchers. In this regard, a vast amount of papers (in various fields) have appeared in the literature (Rodríguez & Montoya, 2009) (Montoya & Vargas, 2011) (Golias, 2013). Theoretical scheduling models are limited to sequence jobs in machines. Generally, the models studied ignore all constraints related to the availability of resources. Nevertheless, in real industrial environment, manufacturing companies encounter resource constraints and jobs need a set of non-renewable resources such as raw materials, during the time to be processed; hence, the consumable resources may be subject to some unavailability periods, which complicate the scheduling problem. In this context, the main objective of industrials is to exploit effectively their manufacturing systems to improve their reactivity and productivity by using all available resources in an optimal way. Indeed, the management of resources remains an inherent phase and it is considered as one of the important strategic tool because it provides many benefits, such as improving production rate and enhancing the system performances.

In the other hand, the reentrant problem is still complex because it reentrant characteristic; which is the ability of the system to process jobs more than once on one or several machines. This field continues to attract the interest of a fair amount of researcher’s because it has a large scope such as system design and inventory control. The reentrant shop environment differs in many aspects from the classical systems. This is due to the fact that many basic problems characteristics in classical scheduling theory do not apply in reentrant shop scheduling. Therefore, in order to consider exploit the system effectively and to improve their performances, the scheduling decisions in production shop should consider all assumptions and constraints as reentrant characteristic and limited resources. Consequently, scheduling problems in such systems are considered as NP-hard because of their inherent difficulties and the presence of many uncertainties. Furthermore, using mathematical analytical methods seems very difficult to solve this kind of problems and there are practically no effective techniques to address all the cases effectively (Garey & Johson, 1979).

This paper which is an extension of works conducted in the literature deals with a simulation study of reentrant parallel machines scheduling problem with consumable resources. It aims to present a mathematical model in order to find the appropriate assignment of jobs to machines and to define the suitable sequencing of jobs assigned to each machine with the consideration of resources requirement and the number of layers to be performed. Additionally, due to its complexity, we adapt an optimization method based on genetic algorithm to address this problem. Subsequently, we study the behavior of several local searches with this metaheuristic in order to improve its performances. On the other hand, this research lead to explore the influences of the reentrant characteristic and availability of resources constraint on the system performances when the proposed metaheuristic is applied. We aim to identify the important decisions points that affect the system behavior, in order to specify the most effective solution.

The remainder of this paper is organized as follows. The next section presents the literature review of the considered problem. Section 3 describes the specificity of the system and the model studied in this research work. The mathematical formulation of the studied system is illustrated in section 4. Then, the resolution approach developed in this study is presented in section 5. Section 6 defines the heuristics procedures adapted to the considered problem. The simulation results are presented in section 7. Finally, the conclusion is offered in section 8.

Complete Article List

Search this Journal:
Open Access Articles
Volume 15: 4 Issues (2022): Forthcoming, Available for Pre-Order
Volume 14: 4 Issues (2021): 2 Released, 2 Forthcoming
Volume 13: 4 Issues (2020)
Volume 12: 4 Issues (2019)
Volume 11: 4 Issues (2018)
Volume 10: 4 Issues (2017)
Volume 9: 4 Issues (2016)
Volume 8: 4 Issues (2015)
Volume 7: 4 Issues (2014)
Volume 6: 4 Issues (2013)
Volume 5: 4 Issues (2012)
Volume 4: 4 Issues (2011)
Volume 3: 4 Issues (2010)
Volume 2: 4 Issues (2009)
Volume 1: 4 Issues (2008)
View Complete Journal Contents Listing