A polynomial algorithm for a two-machine no-wait job-shop scheduling problem |
| |
| Institution: | 1. LSCP, Département d''études cognitives, ENS, EHESS, CNRS, PSL University, 75005 Paris, France;2. Department of Comparative Language Science, Language Development Laboratory, University of Zurich, 8032 Zurich, Switzerland;3. Center for the Interdisciplinary Study of Language Evolution, ISLE, University of Zurich, 8032 Zurich, Switzerland;1. Department of Computer Science and Software Engineering, Swinburne University of Technology, Hawthorn, VIC 3122, Australia;2. School of Computer Science, The University of Nottingham Ningbo China, Ningbo 315100, China;3. Laboratory of Intelligent Computing and Software Engineering, Zhejiang Sci-Tech University, Hangzhou 310018, China |
| |
| Abstract: | This paper considers the no-wait scheduling of n jobs, where each job is a chain of unit processing time operations to be processed alternately on two machines. The objective is to minimize the mean flow time. We propose an O(n6)-time algorithm to produce an optimal schedule. It is also shown that if zero processing time operations are allowed, then the problem is NP-hard in the strong sense. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
