In this thesis, high level metaheuristics are proposed to solve production scheduling problems. Production scheduling is a crucial function for companies, which helps to manage the operations at the production shop level. It aims to reduce the costs, to increase the service level to customers, and to achieve better production efficiency. The design of powerful optimization methods for such problems is then decisive for the competitiveness of the companies. This thesis is divided into five chapters which focus on different production scheduling problems. For each problem, an integer linear programming formulation is given, and various heuristics and metaheuristics are proposed and compared. The first two chapters concern an extension of the graph coloring problem, which is extended to correspond to realistic job scheduling problems. Chapters three and four are related to a single machine scheduling problem. The last chapter studies the integration of short term supply chain management decisions.