Flexible scheduling in cells of a workshop

Some workshops are organized in manufacturing cells, where each cell is a set of machines, under the responsibility of a cell's manager. This person has in charge the management of his cell and the schedule of the tasks on its machines. Each cell's manager has his own objectives and his own information. The problem is to assign operations to cells and to propose a flexible schedule for each of them. The flexibility is given by using the concept of group of permutable operations, that leads to a sequential flexibility, that means some choices for the cell's manager in the processing order of some jobs. Three criteria are considered: the maximum lateness, the provided flexibility and the load balancing between cells. We search for a compromise solution. The problem presented here is issued from a collaboration with OSYS company (www.osys.fr), that is a French company specialized in production control which proposes hardware and software solutions to help in managing workshop activities. The interest of a manufacturing cells organization is to give responsibilities to employees who are often more qualified to answer in real time to unexpected events than a central manager who has only a global view of the workshop. The aim of this study is to provide a scheduling tool for this company. We denote by J = J1, . . . , Jn a set of n jobs to schedule. Each job Ji is composed of ni tasks Oi,j characterized by a duration pi,j . Each job Ji is also characterized by a release date ri and a due date di. The workshop is composed of K cells denoted by Ik. These cells form a partition of M = M1, . . . ,Mm, the set of workshop resources. An operation Oi,j can be processed on any machine that belongs to subset of M denoted by Ri,j . If two successive operations Oi,j and Oi,j+1 of a job Ji are processed on two different cells Ik and I0 k respectively, we consider that a transportation time (k, k0) is required between the completion time of Oi,j and the starting time of Oi,j+1. First, we propose a greedy algorithm to solve the assignment of operations to cells and the scheduling problem inside each cell, without flexibility. In a classical problem instance, 5000 operations have to be scheduled. The solution returned by this algorithm is improved by a Tabu search algorithm, both in terms of quality (lateness) and in terms of load balancing. Then, an algorithm is applied to group operations on machines and thus to provide sequential flexibility, without decreasing the quality of the solution. Algorithms and computational results will be presented during the conference