Piece-Mold-Machine Manufacturing Planning

Related Research

Scheduling problems often consider setup times between the executions of different type of jobs (in our problem jobs can be considered as a type of piece). Moreover, there are cases where the setup times depend, besides the previous scheduled task, on the task to be executed. These are known as sequence dependent setup times (s_ij denotes the setup time between job i and job j). The latter is our case, where the change of type of piece to produce, induces a setup time. Scheduling problems with sequence-dependent setup times are, generally NP-hard (Brucker, 2001) and there exist several solution methods. However, these methodologies are focused on the single machine case (Eren, 2007; Eren & Güner, 2005; Sourd, 2006; Stecco, Cordeau, & Moretti, 2008). We can particularly cite Lou and Chu (2006) who worked in the minimization of the total tardiness scheduling problem on a single machine and sequence-dependent setup times. By using a branch and bound method (B&B) based on permutation schemes, they find exact solutions within reasonable time. This scheduling problem has the characteristic of being non preemptive which prevents a task to be interrupted during its execution. This assumption is not consistent with the characteristics of our problem, besides the use of a single machine.