Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Sadegh Niroomand (Firouzabad Institute of Higher Education, Iran) and Béla Vizvári (Eastern Mediterranean University, North Cyprus, Turkey)

Source Title: Handbook of Research on Modern Optimization Algorithms and Applications in Engineering and Economics

Copyright: © 2016
|Pages: 19
DOI: 10.4018/978-1-4666-9644-0.ch012

Chapter Preview

TopIn manufacturing organizations, goals like profitability, quality of products, on-time delivery, and so on play a critical role in keeping and increasing the market share of organizations. The scheduling of tasks in manufacturing helps to decrease production costs and to shorten the lead time of finished products. Classical scheduling problems are mostly time-based optimization problems, while the processing time and setup time of tasks are assumed to be constant. A well-known type of scheduling problem is known as the single machine scheduling problem, which concerns the arrangement of jobs on a single machine/system considering setup times and processing times of jobs. A good survey of scheduling problems with setup times is presented by Allahverdi *et al*. (2008).

Scheduling problems need efficient mathematical models in order to be solved effectively. Generally, mixed integer linear programming (MILP) models are used for such problems. Pinedo (2008) classifies these scheduling problems as complex optimization problems that belong to NP-hard problems. Floudas and Lin (2005) focused on the application of MILP in process scheduling while Barton and Lee (2004), Kallrath (1999), Lee and Grossman (2003) and Fahmy and ElMekkawy and Balakrishnan (2008) using mixed integer nonlinear programming (MINLP) to formulate scheduling problems. A mixed integer quadratic programming (MIQP) model was also applied by Dua and Morari (2004).

The mathematical models of scheduling problems are divided into two types, discrete and continuous formulations. In discrete formulation, the tasks must be started at the beginning or end of predetermined equal discrete time intervals. Floudas and Lin (2004) focused on the discrete formulation. These models need a large number of binary variables for representing the scheduling problem. They also represent an approximate time domain (Stefansson *et al*. (2011)). On the other hand, continuous formulation allows the tasks to be started at any time under the condition that there is no overlap with other tasks. Most of the researchers used continuous formulations to model scheduling problems, for example, Giannelos and Georgiadis (2002), Harjunkoski and Grossmann (2002), Janak and lin and Floudas (2005), Castro and Grossmann and Novais (2006), and others. Figure 1 shows the arrangement of tasks based on discrete and continuous models.

Different solution approaches, for example exact and non-exact, are used to solve the mathematical model of scheduling problems. A well-known exact approach is Branch and Bound’s method, which can be applied by heuristic algorithms or optimization software, for example Cplex, Xpress, Lingo, and so on. This method was applied by Rios-Mercado *et al*. (1999), Rabadi *et al*. (2004), Dunstall *et al*. (2005), Ranjbar (2013), Neto *et al.* (2013), and so on. Different metaheuristic algorithms, for example simulated annealing (SA), genetic algorithm, tabu search, ant colony, and so on, were proposed as non-exact methods in order to obtain a good feasible solution where the degree of difficulty of the model is high and exact methods are not able to solve the mathematical model in reasonable time. Studies of Gilland (2002), Kim *et al*. (2002), Mendes *et al*. (2002), Bilge *et al*. (2004), Low (2005), Dupuy *et al*. (2005), Ruiz *et al*. (2006), Hendizadeh *et al.* (2007), Valente (2007), Damodaran *et al.* (2009), Wong *et al.* (2012) and Yang and Shen (2012)Yousefi and Yusuff (2013) can be mentioned as authors who have applied metaheuristics to scheduling problems.

Search this Book:

Reset