×

A contribution and new heuristics for open shop scheduling. (English) Zbl 1171.90403

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Shaa, D. Y.; Hsu, C. Y., A new particle swarm optimization for the open shop scheduling problem, Computers and Operations Research, 35, 10, 3243-3261 (2008) · Zbl 1133.90017
[2] Bräsel, H.; Herms, A.; Morig, M.; Tautenhahn, T.; Tusch, T.; Werner, F., Heuristic constructive algorithms for open shop scheduling to minimize mean flow time, European Journal of Operational Research, 189, 3, 856-870 (2008) · Zbl 1146.90406
[3] Andresen M, Bräsel H, Morig M, Tusch J, Werner F, Willenius P. Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop, Mathematical and Computer Modelling 2008; doi:10.1016/j.mcm.2008.01.002; Andresen M, Bräsel H, Morig M, Tusch J, Werner F, Willenius P. Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop, Mathematical and Computer Modelling 2008; doi:10.1016/j.mcm.2008.01.002 · Zbl 1187.90127
[4] Bräsel, H.; Tautenhahn, T.; Werner, F., Constructive heuristic algorithms for the open shop problem, Computing, 51, 95-110 (1993) · Zbl 0796.90031
[5] Brucker, P.; Hurink, J.; Jurisch, B.; Wöstmann, B. A., A branch and bound algorithm for the open-shop problem, Discrete Applied Mathematics, 76, 43-59 (1997) · Zbl 0882.90066
[6] Liaw, C. F., An iterative improvement approach for the nonpreemptive open shop scheduling problem, European Journal of Operational Research, 111, 509-517 (1998) · Zbl 0937.90032
[7] Guéret, C.; Prins, C., Classical and new heuristics for the open-shop problem: a computational evaluation, European Journal of Operational Research, 107, 306-314 (1998) · Zbl 0943.90029
[8] Guéret, C.; Prin, C., A new lower bound for the open-shop problem, Annals of Operations Research, 92, 165-183 (1999) · Zbl 0958.90033
[9] Dorndorf, U.; Pesch, E.; Phan-Huy, T., Solving the open shop scheduling problem, Journal of Scheduling, 4, 157-174 (2001) · Zbl 0991.90068
[10] Liaw, C. F., A hybrid genetic algorithm for the open shop scheduling problem, European Journal of Operational Research, 124, 28-42 (2000) · Zbl 0960.90039
[11] Prins, C., Competitive genetic algorithms for the open shop scheduling problem, Mathematical Methods of Operations Research, 52, 389-411 (2000) · Zbl 1023.90030
[12] Lowa C, Yeh Y. Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated. Robotics and Computer-Integrated Manufacturing 2008; doi:10.1016/j.rcim.2007.07.017; Lowa C, Yeh Y. Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated. Robotics and Computer-Integrated Manufacturing 2008; doi:10.1016/j.rcim.2007.07.017
[13] Naderi B, Zandieh M, Fatemi Ghomi SMT. Scheduling job shop problems with sequence-dependent setup times, International Journal of Production Research 2008; doi:10.1080/00207540802165817; Naderi B, Zandieh M, Fatemi Ghomi SMT. Scheduling job shop problems with sequence-dependent setup times, International Journal of Production Research 2008; doi:10.1080/00207540802165817 · Zbl 1198.90198
[14] Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operations Research, 64, 278-285 (1993) · Zbl 0769.90052
[15] Pinedo, M., Scheduling: theory, algorithms, and systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, USA · Zbl 1145.90393
[16] Sule, D. R., Industrial scheduling (1997), PWS Publishing Company: PWS Publishing Company USA · Zbl 1130.90348
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.