دانلود مقاله ISI انگلیسی شماره 18890
ترجمه فارسی عنوان مقاله

مقایسه برنامه نویسی منطقی محدودیت و حل مشکل توزیع شده: یک مطالعه موردی برای تعامل، کارآمدی و برنامه ریزی تولید کارگاهی قابل اجرا

عنوان انگلیسی
Comparison of constraint logic programming and distributed problem solving: a case study for interactive, efficient and practicable job-shop scheduling
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
18890 2001 25 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Computers & Industrial Engineering, Volume 39, Issues 1–2, February 2001, Pages 187–211

ترجمه کلمات کلیدی
حل مشکل توزیع شده - تولید کارگاهی - زمان بندی -
کلمات کلیدی انگلیسی
Distributed problem solving, Job-shop, Scheduling,
پیش نمایش مقاله
پیش نمایش مقاله  مقایسه برنامه نویسی منطقی محدودیت و حل مشکل توزیع شده: یک مطالعه موردی برای تعامل، کارآمدی و برنامه ریزی تولید کارگاهی قابل اجرا

چکیده انگلیسی

The job-shop scheduling issue is more and more described not only in terms of efficiency (e.g. Makespan), but also in terms of interactivity and practicability. The aim of this paper is to evaluate the ability of two approaches inherited from artificial intelligence domain to contribute to the solving of this issue: Constraint Logic Programming (CLP) on the one hand, and, on the other hand, Distributed Problem Solving (DPS) inherited from Distributed Artificial Intelligence (DAI). This analysis is achieved through the use of two specific computerised tools: Constraint Handling In Prolog (CHIP) as a CLP software and the Distributed Production Scheduling System (DPSS) as a distributed problem solving system. These tools are then evaluated in terms of interactivity, efficiency and practicability. Interactivity is discussed according to qualitative points of view such as the ability to provide efficient decision support, a set of alternative solutions and the possibility to parameterise the algorithms. Efficiency is described in terms of optimality or sub-optimality by the analysis of the Makespan criterion vs. fixed computation time. Practicability is associated to the industrial viability of the methods: ability to cope with real industrial case study or ability to face real industrial contexts. Evaluation is then performed through a multiple criteria analysis. This analysis is achieved given an increasing number of operations to perform. The results highlight the high complementary level of these two approaches, allowing us to provide a framework for a joint integration, which shall be optimised when taking into account the assets of each approach according to the three evaluation criteria.

مقدمه انگلیسی

The domain addressed in this paper is the scheduling of job-shop production systems. A production system can be defined as a system composed of technical and human resources responsible for the physical realisation of products satisfying customers from raw materials or semi-finished products. Each product is described by a manufacturing order, composed of tasks named “operations”. A job-shop production system is characterised by the existence of operations that can be clearly identified and separated, in a discontinuous sense, such as manufacturing systems. Architectures of job-shops are generally more elaborated than continuous production systems (e.g. resource organisation, routing). A production management system is required to elaborate production schedules, to control and to evaluate production progress since: • products must satisfy customers’ needs in terms of quality, functionality, cost and delay; • production systems are characterised by constraints (production times, costs, etc.), limited resources capabilities and suffers from disturbances. Thus we disassociate the production system, responsible for the production progress, from the management system, responsible for the management of the production progress. In this paper, we only focus on the scheduling of the production, that is, we do not deal with design phase nor production activity phase. It is nowadays clear that the need of “intelligent” production management structures continuously increases because of the decrease of product life cycle and the increase of competition. As a consequence, a management system is now evaluated not only in terms of completion time efficiency (product time to market, etc.), inventory level, but also in terms of interactivity in order to integrate all the wishes of the managers (as well as structured or ill- structured wishes) and industrial viability to face the largest number of real production system constraints, whatever their specificity could be. The scope of this paper is then to evaluate two approaches inherited from artificial intelligence, Constraint Logic Programming (CLP) and Distributed Problem Solving (DPS) according to three criteria (axis of significance) listed below: • Scheduling efficiency: we focus in this paper on the Makespan criterion (Cmax), which can be in a first step considered as representative of the efficiency of the scheduling (optimality proved or not). • Interactivity: it has been proved that integration of the human operator in the management system is a way to provide a realistic scheduling elaboration of a job-shop production system (Trentesaux, Moray & Tahon, 1998), implying a need of interaction capability. In this paper, measurement of interactivity refers to the following axis of significance: average time used by the algorithm, capability to modify the parameterisation of the method, tools for decision support, possibility to integrate ill-structured data (lack of knowledge, uncertainty, etc.), existence of any graphic capabilities or ergonomic considerations, level of cooperation performed, etc. • Practicability and industrial viability: that is, the ability of the approach to manage real industrial case studies, to face real industrial contexts and constraints and to manage real sets of data and parameters. The first part deals with the distributed problem solving approach and the Distributed Production Scheduling System (DPSS) tool used while the second one deals with the CLP approach and the Constraint Handling In Prolog (CHIP) tool. The third part details the description of the problem and the evaluation method. We analyse the behaviour (advantages/disadvantages) of both approaches according to the introduced set of criteria where interactivity and efficiency are then evaluated according to the growing number of operations to perform. Practicability is evaluated mainly in terms of existing industrial implementation and software development. The third part gives the results and provides a synthesis that is exploited by the last part in order to provide a general framework for a future joint integration of the two approaches. Some concluding advice is then developed, introducing new research areas aiming at hybridising CLP and DPS approaches. The goal is to find a more adapted approach for efficient and realistic schedules building, with strong capabilities for both interaction with the operator and scheduling efficiency.

نتیجه گیری انگلیسی

This paper has shown that CHIP and DPSS are highly complementary regarding the three criteria used for analysis. As a consequence, a joint integration should be fruitful to provide an effective aid for scheduling. We have enlightened the fact that the best way to hybridise the two approaches is to integrate a CLP algorithm into the DPSS structure, that is, to integrate a local CLP method into each agent. In addition, other works should focus on the analysis of soft-computing technologies (neural networks, genetic algorithms, taboo search, etc.) and on the designing of new evaluation criteria.