A contribution and new heuristics for open shop scheduling

摘要

This paper deals with open shops under makespan minimization. Encoding scheme plays a pivotal role in the success of any algorithm to solve a scheduling problem. Although the permutation list has many advantages (such as high adaptability to any operators, conceptual simplicity and ease of implementation), it suffers from a notorious inherent drawback, called redundancy. This serious drawback has made many researchers conclude that permutation list is ineffective for open shop scheduling. Therefore, they have turned toward the utilization of rank matrix encoding scheme to overcome this shortcoming at the expense of losing other advantages of permutation list. In this paper, we first pinpoint the origin of redundancy in the permutation list. We then analyze circumstances in which the redundancy occurs and afterwards present four efficient theorems to avoid this critical disadvantage. Regarding the theorems, we understand that redundancy is quite identifiable and also controllable. By introducing an alternative possibility to rank matrices of excluding redundancy, the solution space of open shops is significantly reduced. By reducing the search space, the probability of finding an excellent solution in reasonable computational time outstandingly soars. Finally, based on insertion and reinsertion operators we propose four constructive heuristics incorporating simple applications of the theorems. We evaluate the effectiveness and efficiency of our proposed algorithms on three well-known benchmarks and against some other existing heuristics. All the results and analyses illustrate the authenticity and superiority of our theorems and proposed constructive heuristics.