Models and an exact method for the Unrelated Parallel Machine scheduling problem with setups and resources. (April 2020)

• Record Type: Journal Article
• Authors: Fanjul-Peyro, Luis
• Is Part Of: Expert systems with applications. Volume 5(2020)
• Publication Date: 2020-04
• Subjects: Scheduling -- Parallel machines -- Sequence dependent setup times -- Additional resources -- Makespan; 006.33
• DOI: 10.1016/j.eswax.2020.100022
• Languages: English
• ISSNs: 2590-1885

Abstract

Highlights: The problem of unrelated parallel machines with setups and resources is considered. A new mathematical model is presented. A mathematical exact algorithm with 3 phase (Three Phase Algorithm) is proposed. Comprehensive computational tests are carried out. Model with some solutions up to 50 jobs and the Three Phase Algorithm up to 400. Abstract: This paper deals with the Unrelated Parallel Machine scheduling problem with Setups and Resources (UPMSR) with the objective of minimizing makespan. Processing times and setups depend on machine and job. The necessary resources could be: specific resources for processing, needed for processing a job on a machine; specific resources for setups, needed to do the previous setup before a job is processed on a machine; shared resources, understanding these as unspecific resources that could also be needed in both processing or setup. The number of scarce resources depends on machine and job. As an industrial example, in a plastic processing plant molds are the specific resource for processing machines, cleaning equipment is the specific resource for setups and workers are the unspecific shared resource to operate processing machines and setup cleaning equipment. A mixed integer linear program is presented to model this problem. Also a three phase algorithm based on mathematical exact method is introduced. Model and algorithm are tested in a comprehensive and extensive computational campaign. Tests show good results for different combinations of useE of resources and in most cases come to less than 2.7% of gap against lower bound for instances of 400 jobs.