Within projects 200020-109854 and 200020-122110/1 "Approximation Algorithms for Machine Scheduling Through Theory and Experiments" we have inquired into some of the main problems in the area of machine scheduling. What is more, we have considered and successfully addressed well-known open problems. The obtained results have been the first important advances on the open questions stated in [Schuurman and Woeginger'99] which have been open for more than 20 years by now. We now need to focus this investigation to better exploit the competence and the noticeable experience we have developed on the mentioned problems and to verify new ideas: we will investigate possible generalizations and extensions of our previous methods in order to improve and generalize on the results obtained in the previous project, as well as to tackle a set of scheduling problems which are recognized to be the most vexing open questions in the area of scheduling problems. These problems form one of the classes, where tight results are regarded as exceptional. Because of their fundamental importance for analyzing more complex scheduling problems, the understanding of their approximability is among the most prominent open problems in scheduling theory Approximation Algorithms. We would like to continue our investigation on the open questions stated in  which have been open for more than 20 years by now. No tight results are known for these basic scheduling problems, and narrowing the approximability gap is a fundamental question in scheduling. We are interested in studying the approximability, both positive and negative results, for several shop scheduling problems whose status is open from a long time . The theoretical interest of these problems arises because these are basic problems arising in practice. Moreover, another important part of the project is about "techniques". We would like to investigate on the use of Semidefinite Programming (SDP) relaxations for scheduling problems. Even though SDP relaxations have been one of the most important tools in designing approximation algorithms for combinatorial optimization problems for the last several years (see e.g. ), to scheduling problems applications so far have been rare and very limited [1, 16, 74, 108]. Understanding Heuristic Methods. IDSIA has developed many heuristics [49, 95, 12, 87, 48,38, 22, 50, 51, 92, 23] for several problems which have no worst-case guarantees on performance, but do well for "typical" problems. Understanding when and to what extent heuristic methods succeed and fail is a challenge for both theory and practice. Our goal is to combine mathematical rigor and experiments to answer questions such as: What features cause heuristic methods to succeed or fail? Are some methods more powerful than others, or does the preferred method depend on the problem? How can we set the parameters of a heuristic for best performance? In particular, we want a theoretical understanding of when widely used heuristics, like Ant Colony Optimization and Tabu Search (for which IDSIA has developed a noticeable experience [49, 93, 12, 38, 50, 51, 37, 22]) succeed. Within a recent project we obtained the first known results regarding Tabu Search algorithm when applied to Max 2-Sat problem [88,89]. Recently, we showed that ants interactions in Ant Colony Algorithms may help to achieve substantial speedups thanks to a better exploitation of the available problem knowledge. We plan to extend these promising and encouraging results to other metaheuristics and for other problems. The project will be held at Istituto Dalle Molle di Studi Sull'Intelligenza Articiale (IDSIA) with a research team composed by two research assistants for three years, and two PhD students, one for one year, as a continuation of the previous project, and the other for three years.