Earliness-tardiness-lost sales dynamic job-shop scheduling

In the real world production environment, the decision about the acceptance or rejection of new orders is made by both the sale department and the production department, cooperatively. However, as far as we searched, no published paper has considered this fact so far. Job-shop scheduling is one of the most complex problems in scheduling. In job-shop environment, there are some production stations, and every job (order; In this paper job and order are used in the same meaning) has a specific production sequence which is not necessarily the same as the other jobs’ sequences. This paper studies the earliness-tardiness-lost sales dynamic job-shop scheduling problem. In this problem, whenever some new orders arrive, a decision is made about the acceptance or the rejection of each of these orders. In this way, all of the alternatives, including the acceptance or rejection of each new order, should be compared. If at least one new order is accepted, the new schedule which includes the accepted order(s) will be generated. By defining some variables, this comparison is done by the developed models. Because of NP-hardness of this problem, exact methods can not be used to solve it in large or medium scales. So, in this paper a hybrid metaheuristic algorithm is developed, which is composed of a genetic algorithm to determine the sequence of the operations and a simulated annealing algorithm to achieve a near-optimal schedule based on this sequence. Finally, the efficiency and effectiveness of the algorithm is evaluated using some numerical results.