No Access

An Ordered Flow Shop with Two Agents

Department of Business Administration, Chungnam National University, 99 Daehangno, Yuseong-gu, Daejeon 34134, Korea

and

Department of Industrial and Management Systems Engineering, Kyung Hee University, 1732, Deogyeong-daero, Giheung-gu, Yongin-si, Kyunggi-do 17104, Korea

E-mail Address: pmj0684@khu.ac.kr

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0217595916500378Cited by:4 (Source: Crossref)

Abstract

In this paper, we consider a two-agent scheduling problem in an $m$ $m$ -machine ordered flow shop where each agent is responsible for his own set of jobs and wishes to minimize the makespan. Since the problem is NP-hard, we develop a pseudo-polynomial time approach for the case with a fixed number of machines and investigate the conditions that make the problem polynomially solvable. Finally, we consider a three-machine problem with a special processing time structure, and demonstrate its polynomiality.

Keywords:

References

Agnetis, A, PB Mirchandani, D Pacciarelli and A Pacifici (2004). Scheduling problems with two competing agents. Operations Research, 52, 229–242. Crossref, Web of Science, Google Scholar
Agnetis, A, PB Mirchandani, D Pacciarelli and A Pacifici (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150, 3–15. Crossref, Web of Science, Google Scholar
Ahuja, RA, K Mehlhorn, JB Orlin and RE Tarjan (1990). Faster algorithms for the shortest path problem. Journal of the Association for Computing Machinery, 37, 213–223. Crossref, Web of Science, Google Scholar
Arbib, C, S Smriglio and M Servilio (2004). A competitive scheduling problem and its relevance to UMTS channel assignment. Networks, 44, 132–141. Crossref, Web of Science, Google Scholar
Cheng, TCE, CT Ng and JJ Yuan (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 362, 273–281. Crossref, Web of Science, Google Scholar
Hall, NG and CN Potts (2004). Rescheduling for new orders. Operations Research, 52, 440–453. Crossref, Web of Science, Google Scholar
Lee, WC, SK Chen, CW Chen and CC (2011). Wu A two-machine flowshop problem with two agents. Computers & Operations Research, 38, 98–104. Crossref, Web of Science, Google Scholar
Lee, KB, BC Choi, JYT Leung and ML Pinedo (2009). Approximation algorithms for multi-agent scheduling to minimize total weight completion time. Information Processing Letters, 109, 913–917. Crossref, Web of Science, Google Scholar
Leung, JYT, ML Pinedo and G Wan (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458–469. Crossref, Web of Science, Google Scholar
Liua, P, N Yib and X Zhoua (2011). Two-agent single-machine scheduling problems under increasing linear deterioration. Applied Mathematical Modelling, 35, 2290–2296. Crossref, Web of Science, Google Scholar
Luo, W, L Chen and G Zhang (2012). Approximation schemes for two-machine flow shop scheduling with two agents. Journal of Combinatorial Optimization, 24, 229–239. Crossref, Web of Science, Google Scholar
Mor, B and G Mosheiov (2010). Scheduling problems with two competing agents to minimize minmax and minsum earliness measures. European Journal of Operational Research, 206, 540–546. Crossref, Web of Science, Google Scholar
Mor, B and G Mosheiov (2014). Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents, Journal of the Operational Research Society, 65, 151–157. Crossref, Web of Science, Google Scholar
Panwalkar, SS, RA Dudek and ML Smith (1973). Sequencing research and the industrial scheduling problem. In Symposium on the Theory of Scheduling and its Application, SE Elmaghraby (ed.), Springer-Verlag, Berlin and New York, pp. 29–37. Google Scholar
Smith, ML, SS Panwalkar and RA Dudek (1975). Flow shop sequencing problem with ordered processing time matrices. Management Science, 21, 544–549. Crossref, Web of Science, Google Scholar
Smith, ML, SS Panwalkar and RA Dudek (1976). Flow shop sequencing problem with ordered processing time matrices: A general case. Naval Research Logistics Quarterly, 23, 418–486. Crossref, Google Scholar
Tuong, NH, A Soukhal and J-C Billaut (2012). Single-machine multi-agent scheduling problems with a global objective function. Journal of Scheduling, 15, 311–321. Crossref, Web of Science, Google Scholar
Wu, C-C, S-K Huang and W-C Lee (2011). Two-agent scheduling with learning consideration. Computers & Industrial Engineering, 61, 1324–1335. Crossref, Web of Science, Google Scholar
Wu, C-C, W-C Lee and M-J Liou (2013). Single-machine scheduling with two competing agents and learning consideration. Information Sciences, 251, 136–149. Crossref, Web of Science, Google Scholar
Yin, Y, S-R Cheng, T-C-E Cheng, W-H Wu and C-C Wu (2012). Two-agent single-machine scheduling with assignable due dates. Applied Mathematics & Computation, 219, 1674–1685. Crossref, Web of Science, Google Scholar
Yin, Y, S-R Cheng and C-C Wu (2012). Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Information Sciences, 189, 282–292. Crossref, Web of Science, Google Scholar
Yin, Y, S-R Cheng, T-C-E Cheng, W-H Wu and C-C Wu (2013). Two-agent single-machine scheduling with release times and deadlines. International Journal of Shipping and Transport Logistics, 5, 75–94. Crossref, Web of Science, Google Scholar
Yin, Y, T-C-E Cheng, X Yang and C-C Wu (2015). Two-agent single-machine scheduling with unrestricted due date assignment. Computers & Industrial Engineering, 79, 148–155. Crossref, Web of Science, Google Scholar
Yin, Y, T-C-E Cheng, W Long, C-C Wu and L Jun (2015). Two-agent single-machine scheduling with deteriorating jobs. Computers & Industrial Engineering, 81, 177–185. Crossref, Web of Science, Google Scholar
Yin, Y, S-R Cheng, T-C-E Cheng, D-J Wang and C-C Wu (2016). Just-in-time scheduling with two competing agents on unrelated parallel machines. Omega, 63, 41–47. Crossref, Web of Science, Google Scholar
Yin, Y, Y Wang, TCE Cheng, D-J Wang and C-C Wu (2016). Two-agent single-machine scheduling to minimize the batch delivery cost. Computers & Industrial Engineering, 92, 16–30. Crossref, Web of Science, Google Scholar