Title :
Improved interval indexed formulation based heuristic algorithm for scheduling problem
Author :
Yong Ming Wang ; Hong Li Yin
Author_Institution :
Sch. of Manage. & Econ., Kunming Univ. of Sci. & Technol., Kunming, China
Abstract :
Scheduling problems in manufacturing systems and industrial engineering are very complex. If the scale of a problem exceeds a certain threshold, the problem is difficult to solve by traditional or formal optimization approaches. In this paper, scheduling problem is modeled with interval indexed formulation. In the model, intervals formation are very important to the efficiency of the algorithm. We proposed two methods for improving the intervals. First method is increasing time limit approach and the second one is long-short time limit approach. We test our algorithm on a kind of NP-hard problem-single machine total weighted tardiness problem. The results give a validation that the approach we presented have promising to be used to some traditional hard problems, especially, to single machine schuduling problem.
Keywords :
computational complexity; manufacturing systems; optimisation; single machine scheduling; NP-hard problem-single machine total weighted tardiness problem; heuristic algorithm; industrial engineering; interval indexed formulation; long-short time limit approach; manufacturing systems; single machine scheduling problem; Conferences; Decision support systems; Manganese; Heuristic algorithm; Improved algorithm; Interval indexed formulation; Scheduling problem;
Conference_Titel :
Control and Decision Conference (CCDC), 2015 27th Chinese
Conference_Location :
Qingdao
Print_ISBN :
978-1-4799-7016-2
DOI :
10.1109/CCDC.2015.7162245