Change search
Link to record
Permanent link

Direct link
Publications (10 of 132) Show all publications
Forghani, K., Carlsson, M., Flener, P., Fredriksson, M., Pearson, J. & Yuan, D. (2024). Maximizing value yield in wood industry through flexible sawing and product grading based on wane and log shape. Computers and Electronics in Agriculture, 216, Article ID 108513.
Open this publication in new window or tab >>Maximizing value yield in wood industry through flexible sawing and product grading based on wane and log shape
Show others...
2024 (English)In: Computers and Electronics in Agriculture, ISSN 0168-1699, E-ISSN 1872-7107, Vol. 216, article id 108513Article in journal (Refereed) Published
Abstract [en]

The optimization of sawing processes in the wood industry is critical for maximizing efficiency and profitability. The introduction of computerized tomography scanners provides sawmill operators with three-dimensional internal models of logs, which can be used to assess value and yield more accurately. We present a methodology for solving the sawing optimization problem employing a flexible sawing scheme that allows greater flexibility in cutting logs into products while considering product quality classes influenced by wane defects. The methodology has two phases: preprocessing and optimization. In the preprocessing phase, two alternative algorithms are given that generate and evaluate the potential sawing positions of products by considering the 3D surface of the log, product size requirements, and product quality classes. In the optimization phase, a maximum set-packing problem is solved for the preprocessed data using mixed-integer programming (MIP), aiming to obtain a feasible cut pattern that maximizes value yield. This is implemented in a system named FlexSaw, which takes advantage of parallel computation during the preprocessing phase and utilizes a MIP solver during the optimization phase. The proposed sawing methods are evaluated on the Swedish Pine Stem Bank. Additionally, FlexSaw is compared with an existing tool that utilizes cant sawing. Results demonstrate the superiority of flexible sawing. While the practical feasibility of implementing a flexible way of sawing logs is constrained by the limitations of current sawmill machinery, the potential increase in yield promotes the exploration of alternative machinery in the wood industry.

Keywords
Sawing optimization, Wood industry, Maximum set packing, Dynamic programming, Parallel processing
National Category
Mechanical Engineering
Identifiers
urn:nbn:se:ri:diva-68598 (URN)10.1016/j.compag.2023.108513 (DOI)
Funder
Vinnova, 2020–03734
Note

This work was supported by Sweden’s Innovation Agency (VINNOVA) via BioInnovation under grant 2020–03734.

Available from: 2023-12-14 Created: 2023-12-14 Last updated: 2023-12-14
Wessén, J., Carlsson, M., Schulte, C., Flener, P., Pecora, F. & Matskin, M. (2023). A constraint programming model for the scheduling and workspace layout design of a dual-arm multi-tool assembly robot. Constraints
Open this publication in new window or tab >>A constraint programming model for the scheduling and workspace layout design of a dual-arm multi-tool assembly robot
Show others...
2023 (English)In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354Article in journal (Refereed) Epub ahead of print
Abstract [en]

The generation of a robot program can be seen as a collection of sub-problems, where many combinations of some of these sub-problems are well studied. The performance of a robot program is strongly conditioned by the location of the tasks. However, the scope of previous methods does not include workspace layout design, likely missing high-quality solutions. In industrial applications, designing robot workspace layout is part of the commissioning. We broaden the scope and show how to model a dual-arm multi-tool robot assembly problem. Our model includes more robot programming sub-problems than previous methods, as well as workspace layout design. We propose a constraint programming formulation in MiniZinc that includes elements from scheduling and routing, extended with variable task locations. We evaluate the model on realistic assembly problems and workspaces, utilizing the dual-arm YuMi robot from ABB Ltd. We also evaluate redundant constraints and various formulations for avoiding arm-to-arm collisions. The best model variant quickly finds high-quality solutions for all problem instances. This demonstrates the potential of our approach as a valuable tool for a robot programmer. © 2023, The Author(s).

Place, publisher, year, edition, pages
Springer, 2023
Keywords
Assembly manufacturing, Constraint programming, Robot planning and scheduling, Workspace layout design, Constraint theory, Machine design, Robot programming, Dual arm, Layout designs, Planning and scheduling, Robot planning, Robot programs, Sub-problems, Assembly
National Category
Robotics
Identifiers
urn:nbn:se:ri:diva-65715 (URN)10.1007/s10601-023-09345-4 (DOI)2-s2.0-85164960102 (Scopus ID)
Available from: 2023-08-07 Created: 2023-08-07 Last updated: 2023-08-07Bibliographically approved
Frimodig, S., Enqvist, P., Carlsson, M. & Mercier, C. (2023). Comparing Optimization Methods for Radiation Therapy Patient Scheduling using Different Objectives. Operations Research Forum, 4(4), Article ID 83.
Open this publication in new window or tab >>Comparing Optimization Methods for Radiation Therapy Patient Scheduling using Different Objectives
2023 (English)In: Operations Research Forum, ISSN 2662-2556, Vol. 4, no 4, article id 83Article in journal (Refereed) Published
Abstract [en]

Radiation therapy (RT) is a medical treatment to kill cancer cells or shrink tumors. To manually schedule patients for RT is a time-consuming and challenging task. By the use of optimization, patient schedules for RT can be created automatically. This paper presents a study of different optimization methods for modeling and solving the RT patient scheduling problem, which can be used as decision support when implementing an automatic scheduling algorithm in practice. We introduce an Integer Programming (IP) model, a column generation IP model (CG-IP), and a Constraint Programming model. Patients are scheduled on multiple machine types considering their priority for treatment, session duration and allowed machines. Expected future arrivals of urgent patients are included in the models as placeholder patients. Since different cancer centers can have different scheduling objectives, the models are compared using multiple objective functions, including minimizing waiting times, and maximizing the fulfillment of patients’ preferences for treatment times. The test data is generated from historical data from Iridium Netwerk, Belgium’s largest cancer center with 10 linear accelerators. The results demonstrate that the CG-IP model can solve all the different problem instances to a mean optimality gap of less than $$1\%$$within one hour. The proposed methodology provides a tool for automated scheduling of RT treatments and can be generally applied to RT centers.

National Category
Mathematics
Identifiers
urn:nbn:se:ri:diva-67567 (URN)10.1007/s43069-023-00251-2 (DOI)
Available from: 2023-10-27 Created: 2023-10-27 Last updated: 2023-11-16Bibliographically approved
Carlsson, M., Ceschia, S., Di Gaspero, L., Mikkelsen, R. Ø., Schaerf, A. & Stidsen, T. J. (2023). Exact and metaheuristic methods for a real-world examination timetabling problem. Journal of Scheduling
Open this publication in new window or tab >>Exact and metaheuristic methods for a real-world examination timetabling problem
Show others...
2023 (English)In: Journal of Scheduling, ISSN 1094-6136, E-ISSN 1099-1425Article in journal (Refereed) Epub ahead of print
Abstract [en]

We propose a portfolio of exact and metaheuristic methods for the rich examination timetabling problem introduced by Battistutta et al. (in: Hebrard, Musliu (eds) 17th International conference on the integration of constraint programming, artificial intelligence, and operations research (CPAIOR-2020), LNCS, vol 12296. Springer, Berlin, pp 69–81, 2020). The problem includes several real-world features that arise in Italian universities, such as examinations split into two parts, possible requirements of multiple rooms for a single examination, and unavailabilities and preferences for periods and rooms. We developed a CP model encoded in the MiniZinc modeling language and solved it with Gecode, as well as two MIP models solved with Gurobi. The first MIP model is encoded natively and the second one again in MiniZinc. Finally, we extended the metaheuristic method based on simulated annealing of Battistutta et al. by introducing a new neighborhood relation. We compare the different techniques on the real-world instances provided by Battistutta et al., which have been slightly refined by correcting some semantic issues. Finally, we developed a solution checker that is publicly available, together with all instances and solutions, for inspection and future comparisons.

Keywords
Examination timetabling · Constraint programming · Integer programming · Simulated annealing
National Category
Computer Sciences
Identifiers
urn:nbn:se:ri:diva-64418 (URN)10.1007/s10951-023-00778-6 (DOI)
Available from: 2023-05-05 Created: 2023-05-05 Last updated: 2023-06-09Bibliographically approved
Collet, M., Gotlieb, A., Lazaar, N., Carlsson, M., Marijan, D. & Mossige, M. (2020). RobTest: A CP Approach to Generate Maximal Test Trajectories for Industrial Robots. In: 26th International Conference on Principles and Practice of Constraint Programming, CP 2020: . Paper presented at 26th International Conference on Principles and Practice of Constraint Programming, 7 September 2020 through 11 September 2020 (pp. 707-723). Springer Science and Business Media Deutschland GmbH
Open this publication in new window or tab >>RobTest: A CP Approach to Generate Maximal Test Trajectories for Industrial Robots
Show others...
2020 (English)In: 26th International Conference on Principles and Practice of Constraint Programming, CP 2020, Springer Science and Business Media Deutschland GmbH , 2020, p. 707-723Conference paper, Published paper (Refereed)
Abstract [en]

Developing industrial robots which are safe, performant, robust and reliable over time is challenging, because their embedded distributed software system involves complex motions with force and torque control and anti-collision surveillance processes. Generating test trajectories which increase the chance to uncover potential failures or downtime is thus crucial to verify the reliability and performance of the robot before delivering it to its final users. Currently, these trajectories are manually created by test engineers, something that renders the process error-prone and time-consuming. In this paper, we present RobTest, a Constraint Programming approach for generating automatically maximal test trajectories for serial industrial robots. RobTest sequentially calls two constraint solvers: a solver over continuous domains to determine the reachability between configurations of the robot’s 3D-space, and a solver over finite domains to generate maximal-load test trajectories among a set of input points and obstacles of the 3D-space. RobTest is developed at ABB Robotics, a large robot manufacturing company, together with test engineers, who are preparing it for integration within the continuous testing process of the robots product-line. This paper reports on initial experimental results with three distinct solvers, namely Gecode, SICStus and Chuffed, where RobTest, has been shown to return near-optimal solutions for trajectories encounting for more than 80 input points and 60 obstacles in less than 5 min.

Place, publisher, year, edition, pages
Springer Science and Business Media Deutschland GmbH, 2020
Keywords
Global constraints, Industrial robotics, Maximal test trajectories, Path planning, Automatic test pattern generation, Collision avoidance, Constraint theory, Integration testing, Robot programming, Trajectories, Constraint programming, Constraint solvers, Continuous testing, Distributed software system, Near-optimal solutions, Potential failures, Robot manufacturing, Serial industrial robots, Industrial robots
National Category
Natural Sciences
Identifiers
urn:nbn:se:ri:diva-48933 (URN)10.1007/978-3-030-58475-7_41 (DOI)2-s2.0-85091281034 (Scopus ID)9783030584740 (ISBN)
Conference
26th International Conference on Principles and Practice of Constraint Programming, 7 September 2020 through 11 September 2020
Note

Funding details: Norges ForskningsrÃ¥d, UM-MUSE-2020, 274786; Funding text 1: This work is mainly supported by the Research Council of Norway (RCN) through the T-Largo project (Project No.: 274786). Nadjib Lazaar is supported by the project CAR (UM-MUSE-2020).

Available from: 2020-10-15 Created: 2020-10-15 Last updated: 2023-05-05Bibliographically approved
Wessén, J., Carlsson, M. & Schulte, C. (2020). Scheduling of Dual-Arm Multi-tool Assembly Robots and Workspace Layout Optimization. In: Emmanuel Hebrard, Nysret Musliu (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: . Paper presented at 17th International Conference, CPAIOR 2020 Vienna, Austria, September 21–24, 2020 (pp. 511-520). Switzerland, 12296
Open this publication in new window or tab >>Scheduling of Dual-Arm Multi-tool Assembly Robots and Workspace Layout Optimization
2020 (English)In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research / [ed] Emmanuel Hebrard, Nysret Musliu, Switzerland, 2020, Vol. 12296, p. 511-520Conference paper, Published paper (Refereed)
Abstract [en]

The profitability of any assembly robot installation depends on the production throughput, and to an even greater extent on incurred costs. Most of the cost comes from manually designing the layout and proramming the robot as well as production downtime. With ever smaller production series, fewer products share this cost. In this work, we present the dual arm assembly program as an integrated routing and scheduling problem with complex arm-to-arm collision avoidance. We also present a set of high-level layout decisions, and we propose a unified CP model to solve the joint problem. The model is evaluated on realistic instances and real data. The model finds high-quality solutions in short time, and proves optimality for all evaluated problem instances, which demonstrates the potential of the approach.

Place, publisher, year, edition, pages
Switzerland: , 2020
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 12296
Keywords
Assembly manufacturing, Robot planning and scheduling, Constraint programming
National Category
Robotics
Identifiers
urn:nbn:se:ri:diva-48916 (URN)10.1007/978-3-030-58942-4_33 (DOI)978-3-030-58942-4 (ISBN)
Conference
17th International Conference, CPAIOR 2020 Vienna, Austria, September 21–24, 2020
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2020-09-29 Created: 2020-09-29 Last updated: 2023-10-12Bibliographically approved
Castaneda Lozano, R., Carlsson, M., Blindell, G. & Schulte, C. (2019). Combinatorial register allocation and instruction scheduling. ACM Transactions on Programming Languages and Systems, 41(3), Article ID 17.
Open this publication in new window or tab >>Combinatorial register allocation and instruction scheduling
2019 (English)In: ACM Transactions on Programming Languages and Systems, ISSN 0164-0925, E-ISSN 1558-4593, Vol. 41, no 3, article id 17Article in journal (Refereed) Published
Abstract [en]

This article introduces a combinatorial optimization approach to register allocation and instruction scheduling, two central compiler problems. Combinatorial optimization has the potential to solve these problems optimally and to exploit processor-specific features readily. Our approach is the first to leverage this potential in practice: it captures the complete set of program transformations used in state-of-the-art compilers, scales to medium-sized functions of up to 1,000 instructions, and generates executable code. This level of practicality is reached by using constraint programming, a particularly suitable combinatorial optimization technique. Unison, the implementation of our approach, is open source, used in industry, and integrated with the LLVM toolchain. An extensive evaluation confirms that Unison generates better code than LLVM while scaling to medium-sized functions. The evaluation uses systematically selected benchmarks from MediaBench and SPEC CPU2006 and different processor architectures (Hexagon, ARM, MIPS). Mean estimated speedup ranges from 1.1% to 10% and mean code size reduction ranges from 1.3% to 3.8% for the different architectures. A significant part of this improvement is due to the integrated nature of the approach. Executing the generated code on Hexagon confirms that the estimated speedup results in actual speedup. Given a fixed time limit, Unison solves optimally functions of up to 946 instructions, nearly an order of magnitude larger than previous approaches. The results show that our combinatorial approach can be applied in practice to trade compilation time for code quality beyond the usual compiler optimization levels, identify improvement opportunities in heuristic algorithms, and fully exploit processor-specific features.

Place, publisher, year, edition, pages
Association for Computing Machinery, 2019
Keywords
Combinatorial optimization, Instruction scheduling, Register allocation
National Category
Natural Sciences
Identifiers
urn:nbn:se:ri:diva-39654 (URN)10.1145/3332373 (DOI)2-s2.0-85068443848 (Scopus ID)
Note

 Funding details: Vetenskapsrådet, VR, 621-2011-6229; Funding text 1: This article is partially based on preliminary work presented at the Principles and Practice of Constraint Programming (2012) [20]; Languages, Compilers, and Tools for Embedded Systems (2014) [21]; and Compiler Construction (2016) [22]conferences. Compared to the preliminary work, this article is completely restructured and rewritten, completes the combinatorial model with rematerialization, proposes extensions to capture additional program transformations and processor-specific features, and contributes a more exhaustive evaluation. Additions to the evaluation include more benchmarks and processors, evidence of the fundamental benefit of the integrated approach, an in-depth study of scalability, and actual execution measurements. This work has been partially funded by Ericsson AB and the Swedish Research Council (VR) under grant 621-2011-6229. Authors’ addresses: R. C. Lozano, RISE SICS, Electrum 229, Kista, 164 40, Sweden, KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Electrum 229, Kista, 164 40, Sweden; email: roberto.castaneda@ri.se; M. Carlsson, RISE SICS, Electrum 229, Kista, 164 40, Sweden; email: mats.carlsson@ri.se; G. H. Blindell, KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Electrum 229, Kista, 164 40, Sweden; email: ghb@kth.se; C. Schulte, KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Electrum 229, Kista, 164 40, Sweden, RISE SICS, Electrum 229, Kista, 164 40, Sweden; email: cschulte@kth.se. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2019 Association for Computing Machinery. 0164-0925/2019/07-ART17 $15.00 https://doi.org/10.1145/3332373

Available from: 2019-08-07 Created: 2019-08-07 Last updated: 2023-05-05Bibliographically approved
Mossige, M., Gotlieb, A., Spieker, H., Meling, H. & Carlsson, M. (2019). Time-aware test execution scheduling for cyber-physical systems. In: Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI): . Paper presented at 2019 Software Engineering and Software Management, SE/SWM 2019, 18 February 2019 through 22 February 2019 (pp. 121-122). Gesellschaft fur Informatik (GI)
Open this publication in new window or tab >>Time-aware test execution scheduling for cyber-physical systems
Show others...
2019 (English)In: Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI), Gesellschaft fur Informatik (GI) , 2019, p. 121-122Conference paper, Published paper (Refereed)
Abstract [en]

The paper "Time-aware Test Execution Scheduling for Cyber-Physical Systems "first appeared in the application track of the 23rd International Conference on Principles and Practice of Constraint Programming (CP 2017). Testing cyber-physical systems involves the execution of test cases on target-machines equipped with the latest release of a software control system. When testing industrial robots, it is common that the target machines need to share some common resources, e.g., costly hardware devices, and so there is a need to schedule test case execution on the target machines, accounting for these shared resources. With a large number of such tests executed on a regular basis, this scheduling becomes difficult to manage manually. In fact, with manual test execution planning and scheduling, some robots may remain unoccupied for long periods of time and some test cases may not be executed. We introduce TC-Sched, a time-aware method for automated test case execution scheduling. TC-Sched uses Constraint Programming to schedule tests to run on multiple machines constrained by the tests' access to shared resources, such as measurement or networking devices. We will further discuss challenges and requirements encountered when automating testing for industrial robots. 

Place, publisher, year, edition, pages
Gesellschaft fur Informatik (GI), 2019
Keywords
Continuous Integration, Cyber-Physical Systems, Software Testing, Test Scheduling, Computer systems programming, Constraint theory, Cyber Physical System, Embedded systems, Industrial robots, Integration testing, Robot programming, Scheduling, Constraint programming, Continuous integrations, Multiple machine, Networking devices, Principles and practices, Shared resources, Software control systems, Testing
National Category
Natural Sciences
Identifiers
urn:nbn:se:ri:diva-39979 (URN)10.18420/se2019-36 (DOI)2-s2.0-85072109384 (Scopus ID)9783885796862 (ISBN)
Conference
2019 Software Engineering and Software Management, SE/SWM 2019, 18 February 2019 through 22 February 2019
Available from: 2019-10-16 Created: 2019-10-16 Last updated: 2023-05-05Bibliographically approved
Dubois, C., Grinchtein, O., Pearson, J. & Carlsson, M. (2018). Exploring Properties of a Telecommunication Protocol with Message Delay Using Interactive Theorem Prover. In: Einar Broch Johnsen and Ina Schaefer (Ed.), International Conference on Software Engineering and Formal Methods: . Paper presented at International Conference on Software Engineering and Formal Methods (SEFM 2018), part of STAF 2018 (pp. 239-253).
Open this publication in new window or tab >>Exploring Properties of a Telecommunication Protocol with Message Delay Using Interactive Theorem Prover
2018 (English)In: International Conference on Software Engineering and Formal Methods / [ed] Einar Broch Johnsen and Ina Schaefer, 2018, p. 239-253Conference paper, Published paper (Refereed)
Abstract [en]

An important task of testing a telecommunication protocol consists in analysing logs. The goal of log analysis is to check that the timing and the content of transmitted messages comply with specification. In order to perform such checks, protocols can be described using a constraint modelling language. In this paper we focus on a complex protocol where some messages can be delayed. Simply introducing variables for possible delays for all messages in the constraint model can drastically increase the complexity of the problem. However, some delays can be calculated, but this calculation is difficult to do by hand and to justify. We present an industrial application of the Coq proof assistant to prove a property of a 4G protocol and validate a constraint model. By using interactive theorem proving we derived constraints for message delays of the protocol and found missing constraints in the initial model.

Series
Lecture Notes in Computer Science ; 10886
Keywords
Testing of telecommunication protocol; Constraint programming; Formal proof; Coq
National Category
Computer Systems
Identifiers
urn:nbn:se:ri:diva-34224 (URN)10.1007/978-3-319-92970-5_15 (DOI)2-s2.0-85049015507 (Scopus ID)978-3-319-92969-9 (ISBN)978-3-319-92970-5 (ISBN)
Conference
International Conference on Software Engineering and Formal Methods (SEFM 2018), part of STAF 2018
Available from: 2018-07-17 Created: 2018-07-17 Last updated: 2023-05-05Bibliographically approved
Dekker, J. J., Björdal, G., Carlsson, M., Flener, P. & Monette, J.-N. (2017). Auto-tabling for subproblem presolving in MiniZinc. Constraints, 22(4), 512-529
Open this publication in new window or tab >>Auto-tabling for subproblem presolving in MiniZinc
Show others...
2017 (English)In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 22, no 4, p. 512-529Article in journal (Refereed) Published
Abstract [en]

A well-known and powerful constraint model reformulation is to compute the solutions to a model part, say a custom constraint predicate, and tabulate them within an extensional constraint that replaces that model part. Despite the possibility of achieving higher solving performance, this tabling reformulation is often not tried, because it is tedious to perform; further, if successful, it obfuscates the original model. In order to encourage modellers to try tabling, we extend the MiniZinc toolchain to perform the automatic tabling of suitably annotated predicate definitions, without requiring any changes to solvers, thereby eliminating both the tedium and the obfuscation. Our experiments show that automated tabling yields the same tables as manual tabling, and that tabling is beneficial for solvers of several solving technologies.

Keywords
MiniZinc, Modelling methodology, Presolving, Tabling, Artificial intelligence, Constraint model, Original model, Solving performance, Constraint theory
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-32426 (URN)10.1007/s10601-017-9270-5 (DOI)2-s2.0-85020249248 (Scopus ID)
Funder
Swedish Research Council
Note

Funding details: Uppsala Universitet; Funding details: 2015-4910, VR, Vetenskapsrådet

Available from: 2017-10-31 Created: 2017-10-31 Last updated: 2023-05-05Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0003-3079-8095

Search in DiVA

Show all publications