Using the Simulated Annealing to Solve a JIT Scheduling Problem in the Two-Machine Flow Shop

A two-machine permutation flow shop scheduling with n independent jobs and different due dates is considered in this paper. Since this problem is shown to be NP-Hard, We use the simulated annealing to solve this problem. The objective is minimizing the weighted earliness and tardiness that cover JIT concept. We construct our algorithm in four scenarios with considering two Markov chains and two temperature reduction rates. The best scenario is proposed based on the results of computational experiments. A mathematical programming formulation is proposed for the problem, and the solution obtained by proposed SA algorithms are compared with the optimal ones obtained by mathematical model using LINGO software for small size instances. Also the performance of the best scenario is compared by the standard model of genetic algorithm for different sizes problems and its advantages are shown.