Unrelated parallel-machine scheduling to minimize total weighted completion time

This research deals with the unrelated parallel-machine scheduling to minimize total weighted completion time. There are \(N\) jobs, each having a weight and requiring a single stage of processing on one of the \(M\) machines. Because of the attribute and mechanical structure of the machines, the processing time depends on both the job and the machine. A sequence-dependent setup time is required if the type of job scheduled is different from the previous one on the same machine. The required setup time depends on the previous job type, the current job type, and the machine on which the job is processed. Furthermore, the jobs (i.e., orders) from primary customers have rigid due date constraints. In this research, a revised SWPT and improvement procedures are applied to generate a feasible schedule. Three effective heuristics, two based on record-to-record travel (RRT1 and RRT2) and one based on random descent search, are developed to improve the feasible schedule. Computational performance of the proposed heuristics is evaluated through an extensive experiment. Computational results show that RRT1 performs better than the other two heuristics and is able to improve the initial solutions effectively. Computational experiences also indicate that RRT1 is capable of obtaining the optimal solutions for the small-size tested problems very efficiently.