American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2020174

Parallel-machine scheduling in shared manufacturing

Min Ji 1, , Xinna Ye 1, , Fangyao Qian 1, , T.C.E. Cheng 2, and  Yiwei Jiang 1,,

1. 

School of Management and E-Business, Contemporary Business and Trade Research Center, Zhejiang Gongshang University, Hangzhou 310018, Zhejiang, P. R. China
2. 

Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Kowloon, Hong Kong

* Corresponding author: Yiwei Jiang

Received  May 2020 Revised  August 2020 Published  December 2020

Fund Project: This research was supported in part by the National Natural Science Foundation of China under grant numbers 11971434 and 11871327, Zhejiang Provincial Natural Science Foundation of China under grant number LY21G010002, and the Contemporary Business and Trade Research Center of Zhejiang Gongshang University, which is a key Research Institute of Social Sciences and Humanities of the Ministry of Education of China. Cheng was supported in part by The Hong Kong Polytechnic University under the Fung Yiu King - Wing Hang Bank Endowed Professorship in Business Administration

We consider parallel-machine scheduling in the context of shared manufacturing where each job has a machine set to which it can be assigned for processing. Such a set is called the processing set. In the shared manufacturing setting, a job can be assigned not only to certain machines for processing, but can also be processed on the remaining machines at a certain cost. Compared with traditional scheduling with job rejection, the scheduling model under study embraces the notion of sustainable manufacturing. Showing that the problem is NP-hard, we develop a fully polynomial-time approximation scheme to solve the problem when the number of machines is fixed.

Keywords: Scheduling, parallel machines, processing set, shared manufacturing, FPTAS.
Mathematics Subject Classification: 90B35, 90C27.
Citation: Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020174
References:
[1]

S. Adhau, M. L. Mittal and A. Mittal, A multi-agent system for decentralized multi-project scheduling with resource transfers, International Journal of Production Economics, 146 (2013), 646-661.  doi: 10.1016/j.ijpe.2013.08.013.  Google Scholar

[2]

P. A. Albinsson and B. Y. Perera, Alternative marketplaces in the 21st century: Building community through sharing events, Journal of Consumer Behaviour, 11 (2012), 303-315.  doi: 10.1002/cb.1389.  Google Scholar

[3]

S. Amaro, L. Andreu and S. Huang, Millenials' intentions to book on Airbnb, Current Issues in Tourism, 22 (2019), 2284-2298.  doi: 10.1080/13683500.2018.1448368.  Google Scholar

[4]

S. J. Barnes and J. Mattsson, Building tribal communities in the collaborative economy: An innovation framework, Prometheus, 34 (2016), 95-113.  doi: 10.1080/08109028.2017.1279875.  Google Scholar

[5]

T. Becker and H. Stern, Impact of resource sharing in manufacturing on logistical key figures, Procedia CIRP, 41 (2016), 579-584.  doi: 10.1016/j.procir.2015.12.037.  Google Scholar

[6]

R. Belk, Why not share rather than own?, Annals of the American Academy of Political and Social Science, 611 (2007), 126-140.  doi: 10.1177/0002716206298483.  Google Scholar

[7]

R. Belk, Sharing, Journal of Consumer Research, 36 (2010), 715-734.   Google Scholar

[8]

Y. Benkler, Sharing nicely: On shareable goods and the emergence of sharing as a modality of economic production, The Yale Law Journal, 114 (2004), 273-358.  doi: 10.2307/4135731.  Google Scholar

[9]

E. Brandt, A vision for shared manufacturing, Mechanical Engineering, 112 (1990), 52-55.   Google Scholar

[10]

F. Chasin, M. von Hoffen, M. Cramer and M. Matzner, Peer-to-peer sharing and collaborative consumption platforms: A taxonomy and a reproducible analysis, Information Systems and E-Business Management, 16 (2018), 293-325.  doi: 10.1007/s10257-017-0357-8.  Google Scholar

[11]

L. Epstein and A. Levin, Scheduling with processing set restrictions: PTAS results for several variants, International Journal of Production Economics, 133 (2011), 586-595.  doi: 10.1016/j.ijpe.2011.04.024.  Google Scholar

[12]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.  Google Scholar

[13]

J. Hamari, M. Sjöklint and A. Ukkonen, The sharing economy: Why people participate in collaborative consumption, Journal of the Association for Information Science and Technology, 67 (2016), 2047-2059.   Google Scholar

[14]

J. He, J. Zhang and X. Gu, Research on sharing manufacturing in Chinese manufacturing industry, International Journal of Advanced Manufacturing Technology, 104 (2019), 463-476.  doi: 10.1007/s00170-019-03886-w.  Google Scholar

[15]

H. Heinrichs, Sharing economy: A potential new pathway to sustainability, Gaia-ecological Perspectives for Science and Society, 22 (2013), 228-231.  doi: 10.14512/gaia.22.4.5.  Google Scholar

[16]

Y. Huo and J. Y. T. Leung, Parallel machine scheduling with nested processing set restrictions, European Journal of Operational Research, 204 (2010), 229-236.  doi: 10.1016/j.ejor.2009.10.025.  Google Scholar

[17]

K. N. Irvine, L. O'Brien, N. Ravenscroft, N. Cooper, M. Everard, I. Fazey, M. S. Reed and J. O. Kenter, Ecosystem services and the idea of shared values, Ecosystem Services, 21 (2016), 184-193.  doi: 10.1016/j.ecoser.2016.07.001.  Google Scholar

[18]

M. Ji and T. C. E. Cheng, Parallel-machine scheduling with simple linear deterioration to minimize total completion time, European Journal of Operational Research, 188 (2008), 342-347.  doi: 10.1016/j.ejor.2007.04.050.  Google Scholar

[19]

M. Ji and T. C. E. Cheng, Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan, European Journal of Operational Research, 202 (2010), 90-98.  doi: 10.1016/j.ejor.2009.05.021.  Google Scholar

[20]

M. Ji, X. Tang, X. Zhang and T. C. E. Cheng, Machine scheduling with deteriorating jobs and DeJong's learning effect, Computers and Industrial Engineering, 91 (2016), 42-47.   Google Scholar

[21]

M. Ji, Q. Yang, D. Yao and T. C. E. Cheng, Single-machine batch scheduling of linear deteriorating jobs, Theoretical Computer Science, 580 (2015), 36-49.  doi: 10.1016/j.tcs.2015.02.025.  Google Scholar

[22]

B. Jiang and L. Tian, Collaborative consumption: Strategic and economic implications of product sharing, Management Science, 64 (2018), 1171-1188.   Google Scholar

[23]

P. Jiang and P. Li, Shared factory: A new production node for social manufacturing in the context of sharing economy, Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 234 (2020), 285-294.  doi: 10.1177/0954405419863220.  Google Scholar

[24]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 4 (1998), 287-297.   Google Scholar

[25]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for the weighted earliness-tardiness problem, Operations Research, 47 (1999), 757-761.  doi: 10.1287/opre.47.5.757.  Google Scholar

[26]

H. Kurdi, E. Aloboud, S. Alhassan and E. T. Alotaibi, An algorithm for handling starvation and resource rejection in public clouds, Procedia Computer Science, 34 (2014), 242-248.  doi: 10.1016/j.procs.2014.07.018.  Google Scholar

[27]

Z. W. Y. Lee, T. K. H. Chan, M. S. Balaji and A. Y.-L. Chong, Why people participate in the sharing economy: An empirical investigation of Uber, Internet Research, 28 (2018), 829-850.  doi: 10.1108/IntR-01-2017-0037.  Google Scholar

[28]

C. P. Lamberton and R. L. Rose, When is ours better than mine? A framework for understanding and altering participation in commercial sharing systems, Social Science Electronic Publishing, 76 (2011), 109-125.   Google Scholar

[29]

J. Y.-T. Leung and C.-L. Li, Scheduling with processing set restrictions: A survey, International Journal of Production Economics, 116 (2008), 251-262.  doi: 10.1016/j.ijpe.2008.09.003.  Google Scholar

[30]

J. Y.-T. Leung and C.-L. Li, Scheduling with processing set restrictions: A literature update, International Journal of Production Economics, 175 (2016), 1-11.  doi: 10.1016/j.ijpe.2014.09.038.  Google Scholar

[31]

J. Y.-T. Leung and C. T. Ng, Fast approximation algorithms for uniform machine scheduling with processing set restrictions, European Journal of Operational Research, 260 (2017), 507-513.  doi: 10.1016/j.ejor.2017.01.013.  Google Scholar

[32]

K. Li, T. Zhou, B. Liu and H. Li, A multi-agent system for sharing distributed manufacturing resources, Expert Systems with Applications, 99 (2018), 32-43.  doi: 10.1016/j.eswa.2018.01.027.  Google Scholar

[33]

S. Li, Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan, European Journal of Operational Research, 260 (2017), 12-20.  doi: 10.1016/j.ejor.2016.11.044.  Google Scholar

[34]

A. M. Munar and J. K. S. Jacobsen, Motivations for sharing tourism experiences through social media, Tourism Management, 43 (2014), 46-54.  doi: 10.1016/j.tourman.2014.01.012.  Google Scholar

[35]

J. Ou, X. Zhong and X. Qi, Scheduling parallel machines with inclusive processing set restrictions and job rejection, Naval Research Logistics, 63 (2016), 667-681.  doi: 10.1002/nav.21728.  Google Scholar

[36]

A. Paagman, M. Tate, E. Furtmueller and J. de Bloom, An integrative literature review and empirical validation of motives for introducing shared services in government organizations, International Journal of Information Management, 35 (2015), 110-123.  doi: 10.1016/j.ijinfomgt.2014.10.006.  Google Scholar

[37]

M. E. Porter and M. R. Kramer, Creating shared value. Harvard Business Review, Harvard Business Review, 89 (2011), 62-77.   Google Scholar

[38]

J. A. Price, Sharing: The integration of intimate economies, Anthropologica (New Series), 17 (1975), 3-27.  doi: 10.2307/25604933.  Google Scholar

[39]

H. Ryu, M. Basu and O. Saito, What and how are we sharing? A systematic review of the sharing paradigm and practices, Sustainability Science, 14 (2019), 515-527.  doi: 10.1007/s11625-018-0638-2.  Google Scholar

[40]

D. Shabtay, N. Gaspar and M. Kaspi, A survey on offline scheduling with rejection, Journal of Scheduling, 16 (2013), 3-28.  doi: 10.1007/s10951-012-0303-z.  Google Scholar

[41]

S. A. Slotnick, Order acceptance and scheduling: A taxonomy and review, European Journal of Operational Research, 212 (2011), 1-11.  doi: 10.1016/j.ejor.2010.09.042.  Google Scholar

[42]

S. Wang and R. A. Noe, Knowledge sharing: A review and directions for future research, Human Resource Management Review, 20 (2010), 115-131.  doi: 10.1016/j.hrmr.2009.10.001.  Google Scholar

[43]

C. H. Yu, K. Doppler, C. B. Ribeiro and O. Tirkkonen, Resource sharing optimization for device-to-device communication underlaying cellular networks, IEEE Transactions on Wireless Communications, 10 (2011), 2752-2763.   Google Scholar

show all references

References:
[1]

S. Adhau, M. L. Mittal and A. Mittal, A multi-agent system for decentralized multi-project scheduling with resource transfers, International Journal of Production Economics, 146 (2013), 646-661.  doi: 10.1016/j.ijpe.2013.08.013.  Google Scholar

[2]

P. A. Albinsson and B. Y. Perera, Alternative marketplaces in the 21st century: Building community through sharing events, Journal of Consumer Behaviour, 11 (2012), 303-315.  doi: 10.1002/cb.1389.  Google Scholar

[3]

S. Amaro, L. Andreu and S. Huang, Millenials' intentions to book on Airbnb, Current Issues in Tourism, 22 (2019), 2284-2298.  doi: 10.1080/13683500.2018.1448368.  Google Scholar

[4]

S. J. Barnes and J. Mattsson, Building tribal communities in the collaborative economy: An innovation framework, Prometheus, 34 (2016), 95-113.  doi: 10.1080/08109028.2017.1279875.  Google Scholar

[5]

T. Becker and H. Stern, Impact of resource sharing in manufacturing on logistical key figures, Procedia CIRP, 41 (2016), 579-584.  doi: 10.1016/j.procir.2015.12.037.  Google Scholar

[6]

R. Belk, Why not share rather than own?, Annals of the American Academy of Political and Social Science, 611 (2007), 126-140.  doi: 10.1177/0002716206298483.  Google Scholar

[7]

R. Belk, Sharing, Journal of Consumer Research, 36 (2010), 715-734.   Google Scholar

[8]

Y. Benkler, Sharing nicely: On shareable goods and the emergence of sharing as a modality of economic production, The Yale Law Journal, 114 (2004), 273-358.  doi: 10.2307/4135731.  Google Scholar

[9]

E. Brandt, A vision for shared manufacturing, Mechanical Engineering, 112 (1990), 52-55.   Google Scholar

[10]

F. Chasin, M. von Hoffen, M. Cramer and M. Matzner, Peer-to-peer sharing and collaborative consumption platforms: A taxonomy and a reproducible analysis, Information Systems and E-Business Management, 16 (2018), 293-325.  doi: 10.1007/s10257-017-0357-8.  Google Scholar

[11]

L. Epstein and A. Levin, Scheduling with processing set restrictions: PTAS results for several variants, International Journal of Production Economics, 133 (2011), 586-595.  doi: 10.1016/j.ijpe.2011.04.024.  Google Scholar

[12]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.  Google Scholar

[13]

J. Hamari, M. Sjöklint and A. Ukkonen, The sharing economy: Why people participate in collaborative consumption, Journal of the Association for Information Science and Technology, 67 (2016), 2047-2059.   Google Scholar

[14]

J. He, J. Zhang and X. Gu, Research on sharing manufacturing in Chinese manufacturing industry, International Journal of Advanced Manufacturing Technology, 104 (2019), 463-476.  doi: 10.1007/s00170-019-03886-w.  Google Scholar

[15]

H. Heinrichs, Sharing economy: A potential new pathway to sustainability, Gaia-ecological Perspectives for Science and Society, 22 (2013), 228-231.  doi: 10.14512/gaia.22.4.5.  Google Scholar

[16]

Y. Huo and J. Y. T. Leung, Parallel machine scheduling with nested processing set restrictions, European Journal of Operational Research, 204 (2010), 229-236.  doi: 10.1016/j.ejor.2009.10.025.  Google Scholar

[17]

K. N. Irvine, L. O'Brien, N. Ravenscroft, N. Cooper, M. Everard, I. Fazey, M. S. Reed and J. O. Kenter, Ecosystem services and the idea of shared values, Ecosystem Services, 21 (2016), 184-193.  doi: 10.1016/j.ecoser.2016.07.001.  Google Scholar

[18]

M. Ji and T. C. E. Cheng, Parallel-machine scheduling with simple linear deterioration to minimize total completion time, European Journal of Operational Research, 188 (2008), 342-347.  doi: 10.1016/j.ejor.2007.04.050.  Google Scholar

[19]

M. Ji and T. C. E. Cheng, Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan, European Journal of Operational Research, 202 (2010), 90-98.  doi: 10.1016/j.ejor.2009.05.021.  Google Scholar

[20]

M. Ji, X. Tang, X. Zhang and T. C. E. Cheng, Machine scheduling with deteriorating jobs and DeJong's learning effect, Computers and Industrial Engineering, 91 (2016), 42-47.   Google Scholar

[21]

M. Ji, Q. Yang, D. Yao and T. C. E. Cheng, Single-machine batch scheduling of linear deteriorating jobs, Theoretical Computer Science, 580 (2015), 36-49.  doi: 10.1016/j.tcs.2015.02.025.  Google Scholar

[22]

B. Jiang and L. Tian, Collaborative consumption: Strategic and economic implications of product sharing, Management Science, 64 (2018), 1171-1188.   Google Scholar

[23]

P. Jiang and P. Li, Shared factory: A new production node for social manufacturing in the context of sharing economy, Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 234 (2020), 285-294.  doi: 10.1177/0954405419863220.  Google Scholar

[24]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 4 (1998), 287-297.   Google Scholar

[25]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for the weighted earliness-tardiness problem, Operations Research, 47 (1999), 757-761.  doi: 10.1287/opre.47.5.757.  Google Scholar

[26]

H. Kurdi, E. Aloboud, S. Alhassan and E. T. Alotaibi, An algorithm for handling starvation and resource rejection in public clouds, Procedia Computer Science, 34 (2014), 242-248.  doi: 10.1016/j.procs.2014.07.018.  Google Scholar

[27]

Z. W. Y. Lee, T. K. H. Chan, M. S. Balaji and A. Y.-L. Chong, Why people participate in the sharing economy: An empirical investigation of Uber, Internet Research, 28 (2018), 829-850.  doi: 10.1108/IntR-01-2017-0037.  Google Scholar

[28]

C. P. Lamberton and R. L. Rose, When is ours better than mine? A framework for understanding and altering participation in commercial sharing systems, Social Science Electronic Publishing, 76 (2011), 109-125.   Google Scholar

[29]

J. Y.-T. Leung and C.-L. Li, Scheduling with processing set restrictions: A survey, International Journal of Production Economics, 116 (2008), 251-262.  doi: 10.1016/j.ijpe.2008.09.003.  Google Scholar

[30]

J. Y.-T. Leung and C.-L. Li, Scheduling with processing set restrictions: A literature update, International Journal of Production Economics, 175 (2016), 1-11.  doi: 10.1016/j.ijpe.2014.09.038.  Google Scholar

[31]

J. Y.-T. Leung and C. T. Ng, Fast approximation algorithms for uniform machine scheduling with processing set restrictions, European Journal of Operational Research, 260 (2017), 507-513.  doi: 10.1016/j.ejor.2017.01.013.  Google Scholar

[32]

K. Li, T. Zhou, B. Liu and H. Li, A multi-agent system for sharing distributed manufacturing resources, Expert Systems with Applications, 99 (2018), 32-43.  doi: 10.1016/j.eswa.2018.01.027.  Google Scholar

[33]

S. Li, Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan, European Journal of Operational Research, 260 (2017), 12-20.  doi: 10.1016/j.ejor.2016.11.044.  Google Scholar

[34]

A. M. Munar and J. K. S. Jacobsen, Motivations for sharing tourism experiences through social media, Tourism Management, 43 (2014), 46-54.  doi: 10.1016/j.tourman.2014.01.012.  Google Scholar

[35]

J. Ou, X. Zhong and X. Qi, Scheduling parallel machines with inclusive processing set restrictions and job rejection, Naval Research Logistics, 63 (2016), 667-681.  doi: 10.1002/nav.21728.  Google Scholar

[36]

A. Paagman, M. Tate, E. Furtmueller and J. de Bloom, An integrative literature review and empirical validation of motives for introducing shared services in government organizations, International Journal of Information Management, 35 (2015), 110-123.  doi: 10.1016/j.ijinfomgt.2014.10.006.  Google Scholar

[37]

M. E. Porter and M. R. Kramer, Creating shared value. Harvard Business Review, Harvard Business Review, 89 (2011), 62-77.   Google Scholar

[38]

J. A. Price, Sharing: The integration of intimate economies, Anthropologica (New Series), 17 (1975), 3-27.  doi: 10.2307/25604933.  Google Scholar

[39]

H. Ryu, M. Basu and O. Saito, What and how are we sharing? A systematic review of the sharing paradigm and practices, Sustainability Science, 14 (2019), 515-527.  doi: 10.1007/s11625-018-0638-2.  Google Scholar

[40]

D. Shabtay, N. Gaspar and M. Kaspi, A survey on offline scheduling with rejection, Journal of Scheduling, 16 (2013), 3-28.  doi: 10.1007/s10951-012-0303-z.  Google Scholar

[41]

S. A. Slotnick, Order acceptance and scheduling: A taxonomy and review, European Journal of Operational Research, 212 (2011), 1-11.  doi: 10.1016/j.ejor.2010.09.042.  Google Scholar

[42]

S. Wang and R. A. Noe, Knowledge sharing: A review and directions for future research, Human Resource Management Review, 20 (2010), 115-131.  doi: 10.1016/j.hrmr.2009.10.001.  Google Scholar

[43]

C. H. Yu, K. Doppler, C. B. Ribeiro and O. Tirkkonen, Resource sharing optimization for device-to-device communication underlaying cellular networks, IEEE Transactions on Wireless Communications, 10 (2011), 2752-2763.   Google Scholar

[1]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017
[2]

Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243
[3]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004
[4]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (40)
  • HTML views (79)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences