Efficient algorithms for flexible job shop scheduling with parallel machines |
| |
| Authors: | Wieslaw Kubiak Yanling Feng Guo Li Suresh P. Sethi Chelliah Sriskandarajah |
| |
| Affiliation: | 1. Faculty of Business Administration, Memorial University of Newfoundland, St. John's, Canada;2. School of Economics and Management, Beijing University of Posts and Telecommunications, Beijing, China;3. School of Management and Economics, Beijing Institute of Technology, Beijing, China;4. Naveen Jindal School of Management, The University of Texas at Dallas, Dallas, Texas, USA;5. Mays Business School, Texas A&M University, College Station, Texas, USA |
| |
| Abstract: | Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two-center job shop. The first center consists of one machine and the second has k parallel machines. An easy-to-perform approximate algorithm for minimizing the makespan with one-unit-time operations in the first center and k-unit-time operations in the second center is proposed. The algorithm has the absolute worst-case error bound of k − 1 , and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2 . |
| |
| Keywords: | absolute worst-case error bound approximation algorithm flexible job shop scheduling makespan |
|
|
