The complex hybrid flexible flowshop problems in the real-world industries scheduling were researched, including constraints of unrelated machines, skipping some stages etc. Though several researches were done to addr...
详细信息
ISBN:
(纸本)9781467376839
The complex hybrid flexible flowshop problems in the real-world industries scheduling were researched, including constraints of unrelated machines, skipping some stages etc. Though several researches were done to address some of the constraints, modeling these constraints was seldom done simultaneously. This paper modeled the problem in the perspective of constraint programming and solved the problem utilizing the Gecode system. The simulation results showed that our proposed method was efficiently and effectively on solving the complex hybrid flexible flowshop problems. It was the first proposed method to investigate and solve the hybrid flexible flowshop problems using constraint programming.
China Railway is undertaking massive construction and development projects. A reasonable and resource-leveled schedule that allows for adjustments for unforeseen circumstances during construction is critical for manag...
详细信息
China Railway is undertaking massive construction and development projects. A reasonable and resource-leveled schedule that allows for adjustments for unforeseen circumstances during construction is critical for managing railway construction projects. Currently, most construction projects use traditional network planning methods or the Gantt schedule for project management. However, these methods have limited applicability to railway construction projects, which are typically linear. This study uses the linear scheduling method and constraint programming techniques for solving schedule control problems faced during railroad construction. The proposal comprises a schedule control model, scheduling model, and schedule control system;the scheduling model is central to the schedule control model. Characteristics such as high flexibility and practicality facilitate multi-objective optimization during scheduling and modification of the linear schedule. The proposed model and algorithm were validated by comparing results with actual data from a highway construction project and the Urumqi-Dzungaria railway construction project. (C) 2013 Elsevier B.V. All rights reserved.
Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems wi...
详细信息
Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems without estimating parameter values and fixing the exact quantitative dynamics. Traditional applications are the study of the dynamics of physical and biological systems at a higher level of abstraction than that obtained by estimation of numerical parameter values for a fixed quantitative model. Qualitative modelling has been studied and implemented to varying degrees of sophistication in Petri nets, process calculi and constraint programming. In this paper we reflect on the strengths and weaknesses of existing frameworks, we demonstrate how recent advances in constraint programming can be leveraged to produce high quality qualitative models, and we describe the advances in theory and technology that would be needed to make constraint programming the best option for scientific investigation in the broadest sense.
Assessment of the correctness of software models is a key issue to ensure the quality of the final application. To this end, this paper presents an automatic method for the verification of UML class diagrams extended ...
详细信息
Assessment of the correctness of software models is a key issue to ensure the quality of the final application. To this end, this paper presents an automatic method for the verification of UML class diagrams extended with OCL constraints. Our method checks compliance of the diagram with respect to several correctness properties including weak and strong satisfiability or absence of constraint redundancies among others. The method works by translating the UML/OCL model into a constraint Satisfaction Problem (CSP) that is evaluated using state-of-the-art constraint solvers to determine the correctness of the initial model. Our approach is particularly relevant to current MDA and MOD methods where software models are the primary artifacts of the development process and the basis for the (semi-)automatic code-generation of the final application. (C) 2014 Elsevier Inc. All rights reserved.
This paper discusses heterogeneous Network-on-Chip (NoC) design from a constraint programming (CP) perspective and extends the formulation to solving Voltage-Frequency Island (VFI) problem. In general, VFI is a superi...
详细信息
This paper discusses heterogeneous Network-on-Chip (NoC) design from a constraint programming (CP) perspective and extends the formulation to solving Voltage-Frequency Island (VFI) problem. In general, VFI is a superior design alternative in terms of thermal constraints, power consumption as well as performance considerations. Given a Communication Task Graph (CTG) and subsequent task assignments for cores, cores are allocated to the best possible places on the chip in the first stage to minimize the overall communication cost among cores. We then solve the application scheduling problem to determine the optimum core types from a list of technological alternatives and to minimize the make-span. Moreover, an elegant CP model is proposed to solve VFI problem by mapping and grouping cores at the same time with scheduling the computation tasks as a limited capacity resource allocation model. The paper reports results based on real benchmark datasets from the literature. (C) 2014 Elsevier Ltd. All rights reserved.
constraint Databases represent complex data by means of formulas described by constraints (equations, inequations or Boolean combinations of both). Commercial database management systems allow the storage and efficien...
详细信息
constraint Databases represent complex data by means of formulas described by constraints (equations, inequations or Boolean combinations of both). Commercial database management systems allow the storage and efficient retrieval of classic data, but for complex data a made-to-measure solution combined with expert systems for each type of problem are necessary. Therefore, in the same way as commercial solutions of relational databases permit storing and querying classic data, we propose an extension of the Selection Operator for complex data stored, and an extension of SQL language for the case where both classic and constraint data need to be managed. This extension shields the user from unnecessary details on how the information is stored and how the queries are evaluated, thereby enlarging the capacity of expressiveness for any commercial database management system. In order to minimize the selection time, a set of strategies have been proposed, which combine the advantages of relational algebra and constraint data representation. (C) 2014 Elsevier Ltd. All rights reserved.
We consider a real problem faced by a large company providing repair services of office machines in Santiago, Chile. In a typical day about twenty technicians visit seventy customers in a predefined service area in Sa...
详细信息
We consider a real problem faced by a large company providing repair services of office machines in Santiago, Chile. In a typical day about twenty technicians visit seventy customers in a predefined service area in Santiago. We design optimal routes for technicians by considering travel times, soft time windows for technician arrival times at client locations, and fixed repair times. A branch-and-price algorithm was developed, using a constraint branching strategy proposed by Ryan and Foster along with constraint programming in the column generation phase. The column generation takes advantage of the fact that each technician can satisfy no more than five to six service requests per day. Different instances of the problem were solved to optimality in a reasonable computational time, and the results obtained compare favorably with the current practice. (C) 2014 Elsevier B.V. All rights reserved.
Every field should have its Grand Challenges. After discussing some general "why and how" issues, with brief reference to some sample challenges, we devote attention to the challenges raised by the new world...
详细信息
Every field should have its Grand Challenges. After discussing some general "why and how" issues, with brief reference to some sample challenges, we devote attention to the challenges raised by the new world of "BigData" and to some new ways of approaching the classic Grand Challenge of the Holy Grail (where one merely states the problem and the computer solves it). There can, of course, never be a definitive catalogue of Grand Challenges. The ultimate Grand Challenge is for everyone working on constraint programming to look up on occasion from their everyday pursuits to consider how they might contribute to a Grand Challenge, and even to try their hand at formulating their own Grand Challenges.
This paper addresses the crew scheduling problem for a mass rapid transit (MRT) system. The problem is to find a minimum number of duties to cover all tasks while satisfying all the hard and soft scheduling rules. Suc...
详细信息
This paper addresses the crew scheduling problem for a mass rapid transit (MRT) system. The problem is to find a minimum number of duties to cover all tasks while satisfying all the hard and soft scheduling rules. Such rules are complicated in real-world operations and difficult to follow through optimization methods alone. In this paper, we propose a constraint programming (CP)-based approach to solve the problem. The approach involves a CP model for duty generation, a set covering problem model for duty optimization, and alternative ways to identify the final solution in different situations. We applied the proposed CP-based approach to solve a case problem for the Taipei MRT. Case application results using real-world data showed that our approach is capable of reducing the number of daily duties from 58 to 55 and achieving a 5.2 % savings in labor costs. We also incorporated the soft rule considerations into the CP model in order to generate alternative optimum solutions that would improve the workload balance. The coefficient of variation of the work time distribution improves significantly, falling from 21 % to approximately 5 %. Given the CP model's comprehensive coverage of various scheduling rules, our proposed approach and models would also be applicable to other MRT systems.
Purpose: The manuscript presents an investigation into a constraint programming-based genetic algorithm for capacity output optimization in a back-end semiconductor manufacturing company. Design/methodology/approach: ...
详细信息
Purpose: The manuscript presents an investigation into a constraint programming-based genetic algorithm for capacity output optimization in a back-end semiconductor manufacturing company. Design/methodology/approach: In the first stage, constraint programming defining the relationships between variables was formulated into the objective function. A genetic algorithm model was created in the second stage to optimize capacity output. Three demand scenarios were applied to test the robustness of the proposed algorithm. Findings: CPGA improved both the machine utilization and capacity output once the minimum requirements of a demand scenario were fulfilled. Capacity outputs of the three scenarios were improved by 157%, 7%, and 69%, respectively. Research limitations/implications: The work relates to aggregate planning of machine capacity in a single case study. The constraints and constructed scenarios were therefore industry-specific. Practical implications: Capacity planning in a semiconductor manufacturing facility need to consider multiple mutually influenced constraints in resource availability, process flow and product demand. The findings prove that CPGA is a practical and an efficient alternative to optimize the capacity output and to allow the company to review its capacity with quick feedback Originality/value: The work integrates two contemporary computational methods for a real industry application conventionally reliant on human judgement. .
暂无评论