Master thesis position: "Production plan optimization"
Forum 'Emplois' - Sujet créé le 2015-11-12 par Chloé Desdouits
Nowadays, a lot of research works are focused on internet of things and web-services to optimize everyday life. Part of this trend, the Arrowhead ARTEMIS European project aims to enable collaborative automation by networked embedded devices. This internship will take part of this project within the Schneider Electric Work Package about production pilots; and especially on a pilot aiming production flexibility and energy efficiency in a discrete manufacturing process: the production of electrical enclosures, cabinets and accessories at a Schneider Electric production site. The
pilot consists of understanding the energy consumption of the manufacturing process and managing it in order to optimize the energy consumption expressed either in Wh, in euros, or in CO2 emissions. The amount of resources spent in the plant is significant:
the annual costs of energy and water reaches more than 1.6 Me, out of which the major part (62%) is electricity, but the detailed split of this consumption is unknown. The problem we want to study during this internship is the following one: when do we need to schedule production activities in order to produce cabinets on time and to minimize energy-related cost?
Scheduling problems consist of finding starting dates for a set of tasks on different machines. Job-shop scheduling is a restricted case where tasks are grouped in several jobs, within a job, tasks are constrained by a chain-precedence graph, and only a given machine is available for each task. According to Garey et al. (1976), the basic job-shop scheduling problem Jm||Cmax is strongly NP-hard. Although small instances may be solved in a optimal way, real world instances must be handled with approximation techniques. According to Danna (2004), large-scale job-shop problems
with just-in-time criterion are well handled by hybrid local search methods.
The first part of the internship will be dedicated to study the state of the art, beginning with the following references on: job-shop scheduling (Garey et al. (1976)), energy scheduling (Artigues et al. (2009)), justin-
time scheduling (Beck and Refalo (2003)) and local search operators (Vaessens et al. (1996); Balas and Vazacopoulos (1998)).
Then, the trainee will have to understand the method that have been previously developed during the project. This resolution method generates a first feasible solution with a CSP formulation to bootstrap a local search engine. This local search engine has several operators implemented: a swap activities operator, a shift operator and a MIP operator. The code is written in Java and was tested on a public benchmark. The first tests show that most of the best-known solutions were found for these instances.
Afterwards, more local search operators (new ones or those found in the literature) should be added in the existing Java code. The constraint formulation should also be improved, depending on the preferences of the candidate. Finally, new experiments will be done to quantify the efficiency of the improved method. A generic black-box local search solver could also be compared to the method developed from scratch.
This internship will be done in the MAORE team of the LIRMM (Montpellier) and/or in the Schneider Electric A4S team (38TEC, Grenoble) on a five of six months period. A gratification of about 1000e per month will be provided by Schneider Electric. The internship will be supervised by Chloé Desdouits (PhD student), Rodolphe Giroudeau and Eric Bourreau (senior lecturers) and Claude Le Pape (PhD, engineer, manager). Contact: chloe.desdouits@schneider-electric.com .
References
Artigues, C., Lopez, P., and Haït, A. (2009). Scheduling under energy constraints. Proceedings of IESM
2009 in Montreal, Canada.
Balas, E. and Vazacopoulos, A. (1998). Guided local search with shifting bottleneck for job shop scheduling.
Management science, 44(2):262–275.
Beck, J. C. and Refalo, P. (2003). A hybrid approach to scheduling with earliness and tardiness costs. Annals
of Operations Research, 118(1-4):49–71.
Danna, E. (2004). Intégration des techniques de recherche locale à la programmation linéaire en nombres
entiers. PhD thesis, Université d'Avignon et des pays du Vaucluse.
Garey, M. R., Johnson, D. S., and Sethi, R. (1976). The complexity of flowshop and jobshop scheduling.
Mathematics of operations research, 1(2):117–129.
Vaessens, R. J. M., Aarts, E. H., and Lenstra, J. K. (1996). Job shop scheduling by local search. INFORMS
Journal on Computing, 8(3):302–317.
pilot consists of understanding the energy consumption of the manufacturing process and managing it in order to optimize the energy consumption expressed either in Wh, in euros, or in CO2 emissions. The amount of resources spent in the plant is significant:
the annual costs of energy and water reaches more than 1.6 Me, out of which the major part (62%) is electricity, but the detailed split of this consumption is unknown. The problem we want to study during this internship is the following one: when do we need to schedule production activities in order to produce cabinets on time and to minimize energy-related cost?
Scheduling problems consist of finding starting dates for a set of tasks on different machines. Job-shop scheduling is a restricted case where tasks are grouped in several jobs, within a job, tasks are constrained by a chain-precedence graph, and only a given machine is available for each task. According to Garey et al. (1976), the basic job-shop scheduling problem Jm||Cmax is strongly NP-hard. Although small instances may be solved in a optimal way, real world instances must be handled with approximation techniques. According to Danna (2004), large-scale job-shop problems
with just-in-time criterion are well handled by hybrid local search methods.
The first part of the internship will be dedicated to study the state of the art, beginning with the following references on: job-shop scheduling (Garey et al. (1976)), energy scheduling (Artigues et al. (2009)), justin-
time scheduling (Beck and Refalo (2003)) and local search operators (Vaessens et al. (1996); Balas and Vazacopoulos (1998)).
Then, the trainee will have to understand the method that have been previously developed during the project. This resolution method generates a first feasible solution with a CSP formulation to bootstrap a local search engine. This local search engine has several operators implemented: a swap activities operator, a shift operator and a MIP operator. The code is written in Java and was tested on a public benchmark. The first tests show that most of the best-known solutions were found for these instances.
Afterwards, more local search operators (new ones or those found in the literature) should be added in the existing Java code. The constraint formulation should also be improved, depending on the preferences of the candidate. Finally, new experiments will be done to quantify the efficiency of the improved method. A generic black-box local search solver could also be compared to the method developed from scratch.
This internship will be done in the MAORE team of the LIRMM (Montpellier) and/or in the Schneider Electric A4S team (38TEC, Grenoble) on a five of six months period. A gratification of about 1000e per month will be provided by Schneider Electric. The internship will be supervised by Chloé Desdouits (PhD student), Rodolphe Giroudeau and Eric Bourreau (senior lecturers) and Claude Le Pape (PhD, engineer, manager). Contact: chloe.desdouits@schneider-electric.com .
References
Artigues, C., Lopez, P., and Haït, A. (2009). Scheduling under energy constraints. Proceedings of IESM
2009 in Montreal, Canada.
Balas, E. and Vazacopoulos, A. (1998). Guided local search with shifting bottleneck for job shop scheduling.
Management science, 44(2):262–275.
Beck, J. C. and Refalo, P. (2003). A hybrid approach to scheduling with earliness and tardiness costs. Annals
of Operations Research, 118(1-4):49–71.
Danna, E. (2004). Intégration des techniques de recherche locale à la programmation linéaire en nombres
entiers. PhD thesis, Université d'Avignon et des pays du Vaucluse.
Garey, M. R., Johnson, D. S., and Sethi, R. (1976). The complexity of flowshop and jobshop scheduling.
Mathematics of operations research, 1(2):117–129.
Vaessens, R. J. M., Aarts, E. H., and Lenstra, J. K. (1996). Job shop scheduling by local search. INFORMS
Journal on Computing, 8(3):302–317.