Nowadays firms have to tackle an ever increasing global competition as well as an ever-changing market demand fluctuation. Such a stressing condition pushes firms to continuously improve the performance of their production processes as to deliver the finished products as early as possible and at the lowest production cost. Scheduling optimization methods play a key role in manufacturing performance improvement and cost reduction and, as a consequence, they may represent a leading leverage in increasing competitiveness of firms.Since most industrial scheduling problems are highly combinatorial and involve complex decision-making issues, they rarely can be optimally solved in a reasonable amount of time. Further, the computational effort to find a good solution is strongly dependent on the problem size itself. Although mathematical formulations are able to describe a large number of scheduling problems, in practice, they can only solve problems of modest size in a reasonable computational time [1], thus highlighting their vulnerability against most real-world problems. According to [2], algorithms that can find optimal solutions to these hard problems in a reasonable amount of time are unlikely to exist. In the last decades, two different research streams concerning the optimization of real-life scheduling problems have captured the attention of both practitioners and scholars. The former concerns with the integration between heuristics and mathematical programming models [1,3,4] the latter involves tailor-made heuristics and metaheuristics algorithms able to find near-optimal solutions through a quick and at the same time smart exploration of the solution space [5,6,7] This paper deals with a real-life case study from the pharmaceutical industry, which may be assimilated to a kind of parallel-batch scheduling problem wherein a machine can process several parts simultaneously in a batch. To date, the firm handles the short-term scheduling task by means of the production supervisor’s experience. Once the production supervisor receives the planned production target in terms of number of batches and type of products to be produced, he empirically generates an operative schedule by means of a Gantt chart, as to determine both the expected task completion times and the related resource requirements. The present research is motivated by the practical implementation of a decision support system to improve the production scheduling task at the lyophilization department of a pharmaceutical plant located in Italy. The following bullet point summarize the main features pertaining to the investigated real-world scheduling problem:• a batch is composed only by identical parts, i.e. product units of the same type;• the batch size, i.e. the number of parts included in a batch, is known in advance and depends on the product type; thus, the batch processing time is equal to the processing time of the specific product type it holds;• regardless of the product type, sequence dependent setup times and removal times are required for each batch to be processed;• a number of daily time windows due to the workforce interaction must be planned along the expected planning time; during such a time interval neither setups nor removals may occurs;• several constraints inherent to the interactions among time windows, setups and removals have to be fulfilled;Since the problem under investigation is quite different from the regular parallel machine scheduling problem, a holistic optimization strategy has been developed as to manage the multitude of constraints affecting the proposed problem. The complexity of the problem prevents any development of linear programming-based mathematical formulations and, as a result, a tailor-made optimization method based on a Hybrid Genetic Algorithm (HGA) has been proposed. The optimization framework consists of a genetic algorithm that makes full use of a proper initialization heuristic procedure aiming to increase the number of feasible solutions included in the initial population. The same heuristic procedure, named Focused Local Search (FLS), is iteratively applied to the most performing individual as to push the exploitation phase of the optimization algorithm. In addition, both a specific two-stage chromosome representation and a complex decoding procedure have been developed in order to minimize the risk of detecting unfeasible solutions. The effectiveness of the proposed scheduling tool was tested on the basis of an extensive benchmarked analysis, which encompasses other performing metaheuristic procedures. Further, in order to demonstrate both real-world applicability and quality of solutions of the proposed scheduler, a comparison with a set of schedules manually performed by the company supervisor has been carried out.References[1] Kopanos, G. M., Mendez, C.A., Puigjaner, L., 2010. MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry. European Journal of Operational Research, 207, 644-655.[2] Hermann, J., 2006. Handbook of Production Scheduling. Springer Science+Business Media, Inc., New York, NY 10013, USA.[3] Stefansson, H., Sigmarsdottir, S., Jensson, P., Shah, N., 2011. Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry. European Journal of Operational Research, 215, 383-392.[4] Lin, R., and Liao, C.-J., 2012. A case study of batch scheduling for an assembly shop. Int J Production Economics, 139, 473-483.[5] Pearn, W.L., Chung, S.H., Chen, A.Y., Yang, M.H., 2004. A case study on the multistage IC final testing scheduling problem with reentry. Int J Production Economics, 88, 257-267.[6] Loukil, T., Teghem, J., Fortemps, P., 2007. A multi-objective production scheduling case study solved by simulated annealing, European Journal of Operational Research, 179, 709-722.[7] Venditti, L., Pacciarelli, D., Meloni C., A tabu search algorithm for scheduling pharmaceutical packaging operations. European Journal of Operational Research, 202, 538-546.
SOLVING A PARALLEL MACHINE SCHEDULING PROBLEM IN A PHARMACEUTICAL MANUFACTURING ENVIRONMENT THROUGH A HYBRID GENETIC ALGORITHM
COSTA, ANTONIO;
2015-01-01
Abstract
Nowadays firms have to tackle an ever increasing global competition as well as an ever-changing market demand fluctuation. Such a stressing condition pushes firms to continuously improve the performance of their production processes as to deliver the finished products as early as possible and at the lowest production cost. Scheduling optimization methods play a key role in manufacturing performance improvement and cost reduction and, as a consequence, they may represent a leading leverage in increasing competitiveness of firms.Since most industrial scheduling problems are highly combinatorial and involve complex decision-making issues, they rarely can be optimally solved in a reasonable amount of time. Further, the computational effort to find a good solution is strongly dependent on the problem size itself. Although mathematical formulations are able to describe a large number of scheduling problems, in practice, they can only solve problems of modest size in a reasonable computational time [1], thus highlighting their vulnerability against most real-world problems. According to [2], algorithms that can find optimal solutions to these hard problems in a reasonable amount of time are unlikely to exist. In the last decades, two different research streams concerning the optimization of real-life scheduling problems have captured the attention of both practitioners and scholars. The former concerns with the integration between heuristics and mathematical programming models [1,3,4] the latter involves tailor-made heuristics and metaheuristics algorithms able to find near-optimal solutions through a quick and at the same time smart exploration of the solution space [5,6,7] This paper deals with a real-life case study from the pharmaceutical industry, which may be assimilated to a kind of parallel-batch scheduling problem wherein a machine can process several parts simultaneously in a batch. To date, the firm handles the short-term scheduling task by means of the production supervisor’s experience. Once the production supervisor receives the planned production target in terms of number of batches and type of products to be produced, he empirically generates an operative schedule by means of a Gantt chart, as to determine both the expected task completion times and the related resource requirements. The present research is motivated by the practical implementation of a decision support system to improve the production scheduling task at the lyophilization department of a pharmaceutical plant located in Italy. The following bullet point summarize the main features pertaining to the investigated real-world scheduling problem:• a batch is composed only by identical parts, i.e. product units of the same type;• the batch size, i.e. the number of parts included in a batch, is known in advance and depends on the product type; thus, the batch processing time is equal to the processing time of the specific product type it holds;• regardless of the product type, sequence dependent setup times and removal times are required for each batch to be processed;• a number of daily time windows due to the workforce interaction must be planned along the expected planning time; during such a time interval neither setups nor removals may occurs;• several constraints inherent to the interactions among time windows, setups and removals have to be fulfilled;Since the problem under investigation is quite different from the regular parallel machine scheduling problem, a holistic optimization strategy has been developed as to manage the multitude of constraints affecting the proposed problem. The complexity of the problem prevents any development of linear programming-based mathematical formulations and, as a result, a tailor-made optimization method based on a Hybrid Genetic Algorithm (HGA) has been proposed. The optimization framework consists of a genetic algorithm that makes full use of a proper initialization heuristic procedure aiming to increase the number of feasible solutions included in the initial population. The same heuristic procedure, named Focused Local Search (FLS), is iteratively applied to the most performing individual as to push the exploitation phase of the optimization algorithm. In addition, both a specific two-stage chromosome representation and a complex decoding procedure have been developed in order to minimize the risk of detecting unfeasible solutions. The effectiveness of the proposed scheduling tool was tested on the basis of an extensive benchmarked analysis, which encompasses other performing metaheuristic procedures. Further, in order to demonstrate both real-world applicability and quality of solutions of the proposed scheduler, a comparison with a set of schedules manually performed by the company supervisor has been carried out.References[1] Kopanos, G. M., Mendez, C.A., Puigjaner, L., 2010. MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry. European Journal of Operational Research, 207, 644-655.[2] Hermann, J., 2006. Handbook of Production Scheduling. Springer Science+Business Media, Inc., New York, NY 10013, USA.[3] Stefansson, H., Sigmarsdottir, S., Jensson, P., Shah, N., 2011. Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry. European Journal of Operational Research, 215, 383-392.[4] Lin, R., and Liao, C.-J., 2012. A case study of batch scheduling for an assembly shop. Int J Production Economics, 139, 473-483.[5] Pearn, W.L., Chung, S.H., Chen, A.Y., Yang, M.H., 2004. A case study on the multistage IC final testing scheduling problem with reentry. Int J Production Economics, 88, 257-267.[6] Loukil, T., Teghem, J., Fortemps, P., 2007. A multi-objective production scheduling case study solved by simulated annealing, European Journal of Operational Research, 179, 709-722.[7] Venditti, L., Pacciarelli, D., Meloni C., A tabu search algorithm for scheduling pharmaceutical packaging operations. European Journal of Operational Research, 202, 538-546.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
