The Local Search and Experiments of Job-Shop Scheduling Problem
The Job-shop Scheduling Problem is a typical scheduling problem, which is regarded as NP-hard because of its complexity. Improvement based on traditional local search methods is realized with the combination of neighborhood and critical path. Firstly, fea
- PDF / 110,986 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 52 Downloads / 211 Views
The Local Search and Experiments of Job-Shop Scheduling Problem Ning Zhao and Si-yu Chen
Abstract The Job-shop Scheduling Problem is a typical scheduling problem, which is regarded as NP-hard because of its complexity. Improvement based on traditional local search methods is realized with the combination of neighborhood and critical path. Firstly, feasible solution is achieved by heuristic approaches or just randomization. Secondly, makespan optimized solution is achieved by improved local search. Finally, the improved local search method is proved effectively by experiments, moreover the searching process is visible and suits man–machine interaction. Keywords Local search • Job-shop scheduling problem • Man–machine interaction • Critical path
Introduction JSP stands for the Job-shop Scheduling Problem. It means to combine time with jobs closely in order to meet the requirements of the productions’ progress. The result of scheduling directly influences the completion time of products, the arrangement of workers and the utilization rate of machines. In the context of diversified market demand, in order to meet the production modes of multispecies, singleton and small-lot, Flexible Manufacturing and Agile Manufacturing emerged. The production line is more complicated, but the delivery time is shortened. In order to resolve these conflicts, researchers from different fields start to focus on the efficient and accurate JSP. The deterministic job-shop scheduling problem can be briefly described as follows: given a finite set of jobs, each is a finite sequence of operations subjected to precedence constraints, each operation needs to be processed exclusively on a machine from a N. Zhao (*) • S.-y. Chen School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China e-mail: [email protected] R. Dou (ed.), Proceedings of 2012 3rd International Asia Conference on Industrial Engineering and Management Innovation(IEMI2012), DOI 10.1007/978-3-642-33012-4_10, # Springer-Verlag Berlin Heidelberg 2013
89
90
N. Zhao and S.-y. Chen
finite set of machines for a prescribed time interval, the goal is to find a schedule which can complete all operations in the shortest time (Murovec and Suhel 2004). As the augment of the number of jobs and machines, the number of solutions can increase exponentially. Researchers regard this kind of problems as NP-hard (nondeterministic polynomial) (Jain and Meeran 1999). The history of JSP’s study can date back to half a century ago. It is the result of development. Its valuable and challengeable arouse a lot of researchers’ interests to study. The methods to solve JSP have experienced the process of simple to complex, single to multiple and theoretical to practical, and have yielded many excellent results. These algorithms can be divided into two categories: Optimization Algorithms and Approximation Algorithms (Shao-li Dai et al. 1999). Optimization Algorithms can assure an optimal result. It includes methods of operations research (such as branch-and-bound a
Data Loading...
