An algorithm for a biobjective parallel machine problem with eligibility and release and delivery times

Keywords: parallel machines, eligibility, release times, delivery times, Pareto front.The scheduling of parallel machines is a well-known problem in many companies. Nevertheless, not always all the jobs can be manufactured in any machine and the eligibility appears. Based on a real-life situation, we present a company which has three different sets of machines, called as high-level, medium-level and low-level respectively. Besides, there are release times and delivery times related to the respective previous operations and following operations to the main process to be carried in the parallel machines. A set of n jobs to be scheduled on these m parallel machines are also distributed among levels. One job from a level can be manufactured in a machine of the same or higher level. Initially all the jobs are processed on the machines of high level. But a penalty appears when a job is manufactured in a machine different of this initial level. The proposed algorithm solves the problem with two criteria: the minimization of the completion time or makespan, Cmax, and the minimization of the total penalty. The objective is to determine or to approximate the Pareto front. Several alternatives are presented according to different rules to move a job from one machine to another and compared through numerical experiments