Solving a Flowshop Scheduling Problem with Answer Set Programming: Exploiting the Problem to Reduce the Number of Combinations

A distinctive characteristic of combinatorial problems is their massive search space. This huge domain is due to the number of possible solutions that although finit e, grows exponentially with the amount of data. Some typical combinatorial problems are the search fo r the cheapest or shortest paths, internet data packets routing, protein structure prediction, and planni ng and scheduling of resources. In theory it is possible to find the optimal solution for each c ombinatorial problem by conducting an exhaustive search. However, in practice finding an optimal s olution is often an intractable problem, even for problems of modest size. In this paper, Answer Set Programming (ASP) is used to explor e how to solve the scheduling problem for an Automated Wet-etch Station (A WS) of a Semiconduct or Manufacturing System where the optimization objective is the makespan. If a robot is not use d to transfer jobs between baths, the problem can be approximated as a special case of the most general n o-wait scheduling flowshop problem. A flowshop is a multistage production process where all jobs m ust pass through the same stages. There is a set J of jobs with J N jobs in total.