A Genetic Algorithm for Scheduling n Jobs on a Single Machine with a Stochastic Controllable Processing, Tooling Cost and Earliness-Tardiness Penalties

Abstract

Problem statement: In this research, we addressed the problem of minimizing the earliness-tardiness penalties and manufacturing costs of a single machine with a stochastic controllable processing and tooling cost. Approach: We developed a mathematical non-linear integer programming model and its linearised version to find the optimal solution. We introduced a new genome representation in single machine scheduling literature that evolved by a genetic algorithm to solve the problem. The genome representation includes two genes per job, one represents the job starting time and other corresponds to the job processing time. The algorithms were compared based on the solution quality, CPU time and memory consumption in bytes on a set of randomly generated test problems. Results: The results showed that developed algorithms could define the global optimal solution of most scheduling problems with n ≤ 20 jobs. For larger n, the developed genetic algorithm outperforms the math models in terms of solution quality and less CPU seconds while consumes moderate memory kilobytes of 3295 compared with 5058 and 1685 of linear and nonlinear models on the average. Conclusion: The GA's average performance achieves 6.013 related to the lower bound of math linear program whereas nonlinear model achieves an average of 1.034. The GA's performance increases by increasing n compared with other techniques. We hope to expand the developed algorithms for different configurations as parallel and job shops.