An uncertain multi-objective programming model for machine scheduling problem
- PDF / 446,038 Bytes
- 8 Pages / 595.276 x 790.866 pts Page_size
- 43 Downloads / 217 Views
ORIGINAL ARTICLE
An uncertain multi-objective programming model for machine scheduling problem Yufu Ning1,2 • Xiumei Chen1,2 • Zhiyong Wang1,2 • Xiangying Li1,2
Received: 4 November 2015 / Accepted: 8 March 2016 Ó Springer-Verlag Berlin Heidelberg 2016
Abstract This paper discusses a parallel machine scheduling problem in which the processing times of jobs and the release dates are independent uncertain variables with known uncertainty distributions. An uncertain programming model with multiple objectives is obtained, whose first objective is to minimize the maximum completion time or makespan, and second objective is to minimize the maximum tardiness time. A genetic algorithm is employed to solve the proposed uncertain machine scheduling model, and its efficiency is illustrated by some numerical experiments. Keywords Machine scheduling problem Uncertain variable Uncertain programming Genetic algorithm
1 Introduction Machine scheduling problem is concerned with finding an efficient schedule during an uninterrupted period of time for a set of machines to process a set of jobs. Machine scheduling problems arise in a wide field of real life and so are important from both theoretical and practical viewpoints. Since the pioneering work of Johnson [9] and Naughton [23], theory for machine scheduling has been greatly enlarged and improved. In 1977, Lenstra et al. [12] studied the complexity of machine scheduling problems, & Yufu Ning [email protected] 1
School of Information Engineering, Shandong Youth University of Political Science, Jinan 250103, China
2
Key Laboratory of Information Security and Intelligent Control in Universities of Shandong, Jinan 250103, China
and showed that most classical machine scheduling problems were NP-complete. In 1979 Graham et al. [6] proposed an expression of three parameters a j b j c where a, b and c represented machine environment, job characteristic and optimality criteria respectively to describe scheduling problems. In a machine scheduling problem, processing time and release date are important factors that affect scheduling plan. Originally, release dates and processing times were assumed to be exact numbers. A great deal of models and algorithms have been developed, such as Baker and Scudder [2], Mokotoff [22], Lam and Xing [11], Pinedo [27] and Xing et al. [32]. Since in real life processing times and release dates are usually difficult to be crisp numbers, the indeterminacy is taken into account. With the proposition of probability theory by Kolmogorov in 1933, Banerjee [3] was the first who investigated a single machine scheduling problem with random processing times. Later, different machine scheduling problems with random processing times were researched. In 1977, Hodegson [7] described a single machine scheduling problem with random processing times, in which he showed that Lawler’s efficient algorithm was optimal even when the processing times were random. Seo et al. [29] studied the single machine scheduling problem for the objective of minimizing the expected
Data Loading...
