Tight Bounds for Permutation Flow Shop Scheduling

Mathematics of Operations Research - Tập 34 Số 2 - Trang 417-427 - 2009
Viswanath Nagarajan1, Maxim Sviridenko2
1Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213;
2IBM T. J. Watson Research Center, Yorktown Heights, New York 10598

Tóm tắt

In flow shop scheduling there are m machines and n jobs, such that every job has to be processed on the machines in the fixed order 1,…,m. In the permutation flow shop problem, it is also required that each machine process the set of all jobs in the same order. Formally, given n jobs along with their processing times on each machine, the goal is to compute a single permutation of the jobs σ: [n] → [n] that minimizes the maximum job completion time (makespan) of the schedule resulting from σ. The previously best known approximation guarantee for this problem was O((m log m)1/2) [Sviridenko, M. 2004. A note on permutation flow shop problem. Ann. Oper. Res. 129 247–252]. In this paper, we obtain an improved O(min{m1/2,n1/2}) approximation algorithm for the permutation flow shop scheduling problem, by finding a connection between the scheduling problem and the longest increasing subsequence problem. Our approximation ratio is relative to the lower bounds of maximum job length and maximum machine load, and is the best possible such result. This also resolves an open question from Potts et al. [Potts, C., D. Shmoys, D. Williamson. 1991. Permutation vs. nonpermutation flow shop schedules. Oper. Res. Lett. 10 281–284], by algorithmically matching the gap between permutation and nonpermutation schedules. We also consider the weighted completion time objective for the permutation flow shop scheduling problem. Using a natural linear programming relaxation and our algorithm for the makespan objective, we obtain an O(min{m1/2,n1/2}) approximation algorithm for minimizing the total weighted completion time, improving on the previously best known guarantee of εm for any constant ε > 0 [Smutnicki, C. 1998. Some results of the worst-case analysis for flow shop scheduling. Eur. J. Oper. Res. 109 66–87]. We give a matching lower bound on the integrality gap of our linear programming relaxation.

Từ khóa


Tài liệu tham khảo

Chakrabarti S., 1996, Proc. 23rd Internat. Colloquium on Automata, Languages, and Programming (ICALP), 646, 10.1007/3-540-61440-0_166

Chazelle B., 2000, The Discrepancy Method: Randomness and Complexity, 10.1017/CBO9780511626371

Chen B., 1998, Handbook of Combinatorial Optimization, 3, 21

Conway R., 1967, Theory of Scheduling

Czumaj A., 2000, Proc. 32 ACM Sympos. Theory Comput (STOC), 38

Feige U., 1998, Proc. 30th Annual ACM Sympos. Theory Comput. (STOC), 624, 10.1145/276698.276878

10.1007/978-3-540-24587-2_34

10.1057/palgrave.jors.2601784

10.1214/aoap/1177005939

Hall L. A., 1996, Proc. 7th Sympos. Discrete Algorithms, 142

10.1287/moor.22.3.513

10.1137/S0895480199363908

Lawler E. L., 1993, Handbook in Operations Research and Management Science, 4, 445

10.1016/0001-8708(77)90030-5

10.1016/0305-0483(83)90088-9

10.1016/0166-218X(93)90156-I

10.1016/0167-6377(89)90045-X

10.1016/0167-6377(91)90025-K

10.1016/0167-6377(91)90014-G

10.1007/BF01581271

10.1002/jos.96

10.1016/0022-0000(88)90003-7

Röck H., 1983, Methods Oper. Res., 45, 303

10.1016/0166-218X(94)90036-1

Schrijver A., 2003, Combinatorial Optimization: Polyhedra and Efficiency (Algorithms and Combinatorics), 24

10.1137/S009753979222676X

10.1016/S0377-2217(97)00139-2

Sotelo D., Poggi de Aragão M. An approximation algorithm for the permutation flow shop scheduling problem via Erdős-Szekeres Theorem Extensions (2008) Working paper, Catholic University of Rio de Janeiro, Rio de Janeiro

10.1023/B:ANOR.0000030691.65576.28

Vershik A. M., 1977, Dokl. Akad. Nauk SSSR, 233, 1024

Thông tin
Thông tin xuất bản

Mathematics of Operations Research

Tập 34 Số 2

417-427

Thông tin tác giả