In a partial shop scheduling problem the operations of each job have to respect a partial order, which can be different for each job. We study the problem of finding a solution of minimal makespan in partial shops. This problem generalizes many problems which have been studied independently in the literature, such as the group shop scheduling problem, the mixed shop scheduling problem, and the open shop scheduling problem. In this paper we propose a single algorithm which is able to find solutions for the partial shop scheduling problem, including all the above special cases. It combines an effective constructive heuristic, a solution perturbation based on deconstruction and reconstruction, and an improvement method based on the transposition of operations in an iterated tabu search. In computational experiments we evaluate the performance of the algorithm on the partial shop, the group shop, the mixed shop, and the open shop, and compare it to the current best algorithms which have been proposed specifically for these problem variants. We find that the proposed single heuristic can compete with all these heuristics, and for several variants improves the state of the art.

¹ Algorithms and Optimization Group – Instituto de Informática – Universidade Federal do Rio Grande do Sul (UFRGS)

Below you can download the data files presented in the article.

- 1
- Table 4: Results comaring PSS, GSS and MSS .
- 2
- Table in Figure 7: Comparing ITS algorithm with the Hybrid Scatter Search for the PSS problem (Nasiri & Kianfar, 2011b).
- 3
- Table in Figure 8: Comparing ITS with the Tabu search for the GSS problem (Liu et al., 2005).
- 4
- Table in Figure 9: Comparing ITS with the GA/TS search for the GSS problem (Nasiri & Kianfar, 2011a) for the instances based on the test set by Demirkol et al. (1998).
- 5
- Table in Figure 10: Comparing ITS with the GA/TS search for the GSS problem (Nasiri & Kianfar, 2011a) for the instances based on the test set by Taillard (1993).
- 6
- Table in Figure 11: Comparing ITS with the Tabu search for the MSS problem (Liu & Ong, 2004).
- 7
- Table in Figure 12: Comparing ITS with the PSO for OSS problem (Sha & Hsu, 2008) for the instances proposed by Taillard (1993).
- 8
- Table in Figure 13: Comparing ITS with the PSO for OSS problem (Sha & Hsu, 2008) for the instances proposed by Brucker et al. (1997).
- 9
- Table in Figure 14: Comparison of the PSO of Sha & Hsu (2008) to ITS on the OSS instances proposed by Gu´ eret & Prins (1999).
- 10
- Instances: FIle with all available PSS instances.
- 11
- Schedules: File with the best schedules found.