Parallel machine scheduling considering job splitting and machine eligibility

Abstract

In this study, we investigate unrelated parallel machine problem with total tardiness objective. The properties of the problem are job splitting, family dependent setup structure and machine eligibility. Job splitting means that jobs can be splitted to be produced on different machines and in different times. Family dependent setup means that a setup is needed before producing a particular family if it is preceded by another family. Machine eligibility means that jobs can’t be produced on all machines, but only the ones that are appropriate for producing them. We propose a heuristic solution method consisting of three phases. In the first phase, jobs belonging to a family are combined into job batches. When making this aggregation, in order to decide the point to stop aggregation, we have two control parameters. These control parameters do not need to be the same for each family. After finishing Phase-1, generated job batches are used as inputs to phase-2. In phase- 2, a new time structure is created based on the due dates of these aggregate jobs. Also in phase-2, an aggregate planning model is constructed and solved yielding production quantities in time buckets. These production quantities are used in Phase-3 for creating job batches which constructs schedule. For examining the performance of our heuristic, we compare it with a heuristic in the literature in which control parameters used in the first phase are the same for all families. According to experimentation results, our heuristic out performs the existing heuristic.