A review on Decisions Support Systems for Manufacturing Scheduling

1 A review on Decisions Support Systems for Manufacturing Scheduling Dios, M. 1 and Framinan, Jose M. 2 1 University of Seville, Spain [email protected] 2 University of Seville, Spain [email protected] Keywords: Decision Support System, DSS, production, scheduling. 1 Introduction There is a widely recognised gap between research and practice in the scheduling eld (MacCarthy and Liu 1993). Among the dierent causes cited, the lack of an integrated view of scheduling has been frequently mentioned (Herrmann 2004), with most research focusing exclusively on technical i.e. optimisation aspects of scheduling. In this regard, Decision Support Systems (DSSs) for scheduling have been acknowledged as a key to integrate human and technical perspectives, thus providing a direction to advance in bridging the aforementioned gap. Therefore, within the scheduling eld there is a growing interest in DSS, which has produced a number of case-studies and descriptions of implementation of DSSs for manufacturing scheduling. The analysis of these case studies and contributions may serve to identify a number of relevant issues still not properly addressed and thus provide future research lines to close the gap between theory and practice in manufacturing scheduling. In addition, such analysis may provide a retrospective study on which techniques and approaches to model scheduling problem are been succesfully implemented in practice. The goal of this paper is to review and classify these contributions. To do so, we rst carry out a systematic review to identify the relevant papers in the literature. In total, 86 contributions have been regarded as relevant. In order to provide a coherent taxonomy for the analysis of these papers, we develop a classication based in the works by (Monfared and Yang 2007, Framinan and Ruiz 2010, Framinan and Ruiz 2012). More specically, we focus on the structure or functionalities of the DSSs reviewed (i.e. what the systems do), and on their methodology (i.e. how the systems achieve their functionality). The rst aspect is oriented towards the identication of issues not adequately covered up-to-now, and the second aspect is related to analysing the degree of success of the diferent techniques and methods available. Due to space problems, the complete classication will be presented in the conference (the full tables with the classication are available in http://taylor.us.es/componentes/mdr/PMS/Review_PMS_2014.pdf ), and here we simply briey discuss the classication criteria and comment some conclusions. 2 Structure of DSS As mentioned before, the structure of the DSSs refers to their functionalities which are classied here according to the architecture of manufacturing scheduling systems by (Framinan and Ruiz 2010):  Scope of the System , i.e the extent of the decisions supported by the system. Although this paper focuses on manufacturing scheduling (S), some DSSs also address related decisions, most typically Planning (P) and Control(C). 76 2  Problem Modeling . This functionality relates to the ability of the system to capture the dierent constraints and features of the shop oor, which can be facilitated by the so-called Model Detection (MD), i.e. DSS' capabilities to determine the most suitable model for solving a specic scheduling scenario. Another feature is Constraints Abstraction (CA), indicating whether the system can reduce the complexity of the models by means of e.g. aggregating constraints.  Problem Solving . This functionality relates to the ability of the system to solve the models. The following specic features can be identied (Framinan and Ruiz 2010): • Algorithms for Rescheduling (AR), which refers to the capability of the DSS for reacting to disturbances by applying the corresponding algorithms. • Multi Algorithm (MA) scheduling, a feature allowing the decision maker to compare the dierent solutions and choose the one tting his/her objectives better. • Evaluation of Algorithms (EA) can be seen as a renement of the previous feature, as the system suggests the planner which one is the best algorithm available. • Generation of New Algorithms (GNA), meaning the capability of the system to embed new algorithms. • Incorporation of Human Expertise (HE), indicating that the DSS allows the decision maker to incorporate his/her expertise in some manner.  Solution Evaluation . This functionality refers to the ability of the system to present the solutions from dierent points of view so the decision maker can analyse them. Dierent features can be considered: • Dierent Objectives (DO). Note that this feature does not refer to considering different objectives in the solution procedure, but on evaluating the resulting schedules with respect to dierent objectives. • Analysis of Scenarios (AS) oers the decision maker the possibility of comparing dierent solutions obtained from the DSS. By means of this feature the decision maker can modify the input data of the DSS to see what happens if, for example, there are more customer orders or if the duration of a task in a specic machine is increased.  User Interface . In this functionality the DSSs show the resulting schedules to the user. Dierent charts and graphs can be used, including Gantt Charts (GC), Job Screens (JS), Machine Loading Boards (MLB), Textual Information (T) or other kinds of charts or diagrams (OC). 3 Methodology of DSS With respect to the methodology adopted in the dierent DSSs in order to provide the functionalities described in Section 2, we use the classication by (Monfared and Yang 2007). In their work, three dierent levels of methodologies are described, i.e.: supporting discipline, major approaches, and techniques. In the rst level  disciplines, they consider Computer Science (CS), Operations Research (OR), and Control Theory (CT). For each supporting discipline, one or more of the dierent major approaches can be adopted: Optimization Techniques (OT), Articial Intelligence (IT), Simulation (S) and Neural Networks (NN). Finally, within each approach, dierent techniques can be applied:  Regarding Optimization Techniques, we distinguish between Mixed Integer Linear Programming (MILP), and approximate techniques such as metaheuristics, i.e.: Tabu Search (TS), Genetic Algorithms (GA), Simulated Annealing (SA) or Specic Heuristics (SH) developed for the problem.  Regarding Simulation, we ideny some contributions using Discrete Event Simulation (DES) and Queuing Theory (QT). 77 3  Regarding Artical Intelligence, three dierent techniques are considered: Expert Systems (ES), Constraint Programming (CP) and Multi-Agents Systems (MAS).  Regarding Neural Networks, we distinguish between Feed Forward Neural Network (FF) and Multi-Layered Perceptron (MLP). 4 Conclusions A number of general conclusions that can be drawn are summarised next:  Regarding the integration of scheduling and related decisions, 28 DSSs address production scheduling and control, in four cases planning and scheduling are simultaneously solved, and in an additional case, scheduling and transport decisions are integrated. We also nd two cases where planning, scheduling and control are faced together.For the rest of the cases, manufacturing scheduling is addressed in isolation. This fact speaks for the relatively autonomy of manufacturing scheduling decisions, which certainly eases the development of DSSs.  When analysing the functional features of the reviewed DSSs, there is a wide diversity in the number and type of features. Problem Modelling is present only in about 27% of the systems, while Problem Solving in more than half of them. Finally, Solution Evaluation and User Interface features are described in around 60% of the systems. A conclusion is that there are few described DSSs addressing the whole process, from modeling to solution representation (only 20%). Most DSSs focus on modelling and solving the models, and do not include information on data management or user interfaces. This makes dicult to transfer the knowledge generated by the authors of these contributions to the real industry. With respect to the structure of the DSS, the following specic conclusions can be presented:  Regarding Problem Modelling, only 26 out of the 86 DSSs include some feature related to this aspect. Moreover, only seven references describe a system with capabilities of Model Detection. If this nding is aligned with the fact that most solution procedures in the literature are model-specic, then it is clear that this functionality is clearly an area in urgent need of research to close the gap between theory and practice.  With respect to Problem Solving, the importance of incorporating human expertise in production scheduling is acknowledged in most DSSs (52%). Algorithms for rescheduling are present in more than 25%. In constrast, the rest of the related features seldomly appear in the DSSs reviewed, all of them referring to algorithms creation, maintenance and evaluation. Since these aspects greatly inuence the capability of adapting a DSS to dierent scheduling scenarios, this factor is probably limiting the expansion of generic manufacturing scheduling DSSs.  Regarding Solution Evaluation, there is a lack of DSSs dealing with stochasticity, as no single contribution was found in this respect. Additionally, a half of the DSSs give the user the possibility to analyse dierent scenarios to get insights about how to enhance his schedules, and around one quarter allows the user for selecting dierent objectives to generate their schedules.  User Interface. It is particularly dicult to infer information regarding this feature obtain as most of the works do not include screenshots of the DSSs nor descriptions about how these present the information to the decision maker. Based on the available information we obtained that a 33.7% of the results used text to show the schedules while almost the half of them show their results through Gantt Charts and around 10% using Job Screens or Machine Loading Boards. There were some works where the information was oered through dierent methods. 78 4 The following conclusions can be extracted regarding the methodology of the DSS:  Regarding the supporting discipline, most DSSs in practice do not adopt a single supporting discipline, but rely on several supporting disciplines depending on the part of the DSS. When addressing issues related to database management components or dialogue management components, the most used discipline is Computer Science, whereas for the model management components the most employed discipline is Operations Research. Finally, Control Theory is predominant for those systems including reactive scheduling. This speaks for the need of an integrated approach and for interdisciplinary teams when trying to comprehensively address the design and implementation of DSSs for manufacturing scheduling.  Regarding approaches for modeling the scheduling problem, there is a strong correlation between the supporting discipline and the approach adopted, although this is not strictly required according to the work by (Monfared and Yang 2007). Perhaps not surprisingly, most DSSs using Optimization Techniques involve minimisation problems, while approaches based on Articial Intelligence and Neural Networks are oriented towards the obtention of feasible schedules. This reveals an apparent lack of interest from the Operations Research approaches to focus on obtaining feasible (but not neccesarily optimal) schedules, as well as the diculty for approaches derived from Computer Science to eciently handle optimisation approaches. Finally, with respect to the specic techniques employed, several remarks can be done:  Deterministic techniques are preferred in front of techniques explicitly addressing the stochastic nature of most scheduling problems. While this does not neccessarily mean that such stochastic nature is ignored in most DSSs, it leads to the need of investigating the degree of variability that deterministic techniques can cope with, i.e. how dierent sources of variability aect the quality of the schedules provided by deterministic techniques.  The majority (39) of the DSSs use Specic Heuristics for the models, which are obviously dicult to be generalized or applied for dierent scenarios. This may point out to the need of moving towards at least two directions: 1) the generalisation of ad hoc techniques so they can be applied to a broader range of situations, and 2) the development of systematic approaches eciently building and testing specic heuristics so the usually high eort to develop and evaluate heuristics for new scheduling problems can be shortened. References MacCarthy, B. L. and Liu, J., 1993, Addressing the gap in scheduling research: A review of optimization and heuristic methods in production scheduling, International Journal of Production Research , Vol. 31(1), pp. 59-79. Hermann J.W., 2004, Information ow and decision-making in production scheduling", IIE Annual Conference and Exhibition 2004 , pp. 1811-1816. Monfared M.A.S., J.B. Yang, 2002, Design of integrated manufacturing planning, scheduling and control systems: a new framework for automation", The international Journal of Advanced Manufacturing Technology , Vol. 33, pp. 545-559. Framinan J.M., R. Ruiz, 2010, Architecture of manufacturing scheduling systems: Literature review and an integrated proposal ", European Journal of Operational Research , Vol. 205, pp. 237-246. Framinan J.M., R. Ruiz, 2012, Guidelines for the deployment and implementation of manufacturing scheduling systems ", International Journal of Production Research , Vol. 50, pp. 1799-1812. 79