A cloud-based simulated annealing algorithm for order acceptance problem with weighted tardiness penalties in permutation flow shop scheduling

Zandieh, M.; Asgari Tehrani, M.M.

A cloud-based simulated annealing algorithm for order acceptance problem with weighted tardiness penalties in permutation flow shop scheduling

Document Type : Original Article

Authors

M. Zandieh ¹

M.M. Asgari Tehrani ²

¹ Department of Industrial Management, Faculty of Management and Accounting, Shahid Beheshti University, G.C., Tehran, Iran.

² Department of Industrial Management, Faculty of Management and Accounting, Shahid Beheshti University, G. C., Tehran, Iran.

Abstract

Make-to-order is a production strategy in which manufacturing starts only after a customer's order is received; in other words, it is a pull-type supply chain operation since manufacturing is carried out as soon as the demand is confirmed. This paper studies the order acceptance problem with weighted tardiness penalties in permutation flow shop scheduling with MTO production strategy, the objective function of which is to maximize the total net profit of the accepted orders. The problem is formulated as an integer-programming (IP) model, and a cloud-based simulated annealing (CSA) algorithm is developed to solve the problem. Based on the number of candidate orders the firm receives, fifteen problems are generated. Each problem is regarded as an experiment, which is conducted five times to compare the efficiency of the proposed CSA algorithm to the one of simulated annealing (SA) algorithm previously suggested for the problem. The experimental results testify to the improvement in objective function values yielded by CSA algorithm in comparison with the ones produced by the formerly proposed SA algorithm.

Keywords

Permutation flow shop scheduling

order acceptance

weighted tardiness

cloud-based simulated annealing algorithm

make-to-order production strategy

20.1001.1.2476308.2014.1.1.1.5

Deyi L., Kaichang D., Deren L., 2000, Knowledge representation and uncertainty reasoning in GIS based on cloud theory, Proceedings of the 9th international symposium on spatial data handling:3–14.
Cesaret B., Og˘uz C., Salman F.S., 2012, A Tabu Search algorithm for order acceptance and scheduling, Computers & Operations Research 39:1197–1205.
Chanas S., Kasperski A., 2001, Minimizing maximum lateness in a single machine scheduling problem with fuzzy processing times and fuzzy due dates, Engineering Applications of Artificial Intelligence 143:377–386.
Cheng J., Steiner G., Stephenson P., 2001, A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times, European Journal of Operational Research 130:559–575.
Cheng T., Li Z., Deng M., Xu Z., 2005, Representing indeterminate spatial objects by cloud theory, Proceedings of the 4th international symposium on spatial data quality:70–77.
De P., Ghosh J.B., Wells C.E., 1993, Job selection and sequencing on a single-machine in a random environment, European Journal of Operational Research 70:425–431.
Deyi L., Cheung D., Xuemei S., Ng V., 1998, Uncertainty reasoning based on cloud models in controllers, Computers and Mathematics with Applications 35:99–123.
Deyi L., Haijun M., Xuemei S., 1995,Membership clouds and membership cloud generators, Journal of Computer Research and Development 32:15–20.
Deyi L., Yi D., 2005, Artificial intelligence with uncertainty, Chapman and Hall.
Du J., Leung J.Y.-T., 1990, Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research 15:483–495.
Ebben M.J.R., Hans E.W., Olde Weghuis F.M., 2005, Workload based order acceptance in job shop environments, OR Spectrum 27:107–122.
Feizhou Z., Yuezu F., Chengzhi S., Deyi L., 1999, Intelligent control based membership cloud generators, Acta Aeronaut Astronaut Sinica, 20:89–92.
Ghosh J.B., 1997 Job selection in a heavily loaded shop, Computers & Operations Research 24:141–145.
Gupta S.K., Kyparisis J., Ip C. M., 1992, Note—Project selection and sequencing to maximize net present value of the total return, Management Science 38:751–752.
Iva˘nescu V.C., Fransoo J.C., Bertrand J.W.M., 2002, Make-span estimation and order acceptance in batch process industries when processing times are uncertain, OR Spectrum 24:467–495.
Iva˘nescu V.C., Fransoo J.C., Bertrand J.W.M., 2006, A hybrid policy for order acceptance in batch-process industries, OR Spectrum 28:199–222.
Johnson S.M., 1954 Optimal two-and three-stage production schedules with set up times included, Naval Research Logistics Quarterly 1:61–68.
Kaichang D., Deyi L., Deren L., 1998, Knowledge representation and discovery in spatial databases based on cloud theory, International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 32:544–551.
Kaichang D., Deyi L., Deren L., 1999, Cloud theory and its applications in spatial data mining knowledge discovery, Journal of Image and Graphics, 4:930–935.
Kirkpatrick S., Gelatt Jr. C.D., Vecchi M.P., 1983, Optimization by simulated annealing, Science 220: 671–680.
Ladhari T., HaouariM. , 2005, A computational study of the permutation flow shop problem based on a tight lower bound, Computers & Operations Research 32:1831–1847.
Lewis H.F., Slotnick S.A., 2002, Multi-period job selection: planning work loads to maximize profit, Computers & Operations Research 29:1081–1098.
Metropolis N., Rosenbluth A., Teller A., Teller E., 1953, Equation of state calculations by fast computing machines, The Journal of Chemical Physics 21:1087–1092.
Niu Q., Jiao B., Gu X., 2008, Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time, Applied Mathematics and Computation 205:148–158.
Og˘uz C., Salman F.S., Yalçın Z.B., 2010, order acceptance and scheduling decisions in make-to-order systems, International Journal of Production Economics 125:200–211.
Potts C.N. , Shmoys D.B., Williamson D.P., 1991 Permutation vs. non-permutation flow shop schedules, Operations Research Letters 10: 281–284.
Pourbabai B., 1989, A short term production planning and scheduling model, Engineering Costs and Production Economics 18:159–167.
Pourbabai B., 1992, Optimal selection of orders in a just-in-time manufacturing environment: a loading model for a computer integrated manufacturing system, International Journal of Computer Integrated Manufacturing 5:38–44.
Ribas I., Leisten R., Framiñan J.M., 2010, Review and classification of hybrid flow-shop scheduling problems from a production system and a solutions procedure perspective, Computers & Operations Research 37:1439–1454.
Rom W.O., Slotnick S.A., 2009, Order acceptance using genetic algorithms, Computers & Operations Research 36:1758–1767.
Roundy R., Chen D., Chen P., Cakanyildirim M., Freimer M.B., Melkonian V., 2005, Capacity-driven acceptance of customer orders for a multi-stage batch manufacturing system: models and algorithms, IIE Transactions 37:1093–1105.
Shuliang W., Deren L., Wenzhong S., Deyi L., Xinzhou W., 2003, Cloud model-based spatial data mining, Geographic Information Sciences, 9:67–78.
Slotnick S.A., Morton T.E., 1996, Selecting jobs for a heavily loaded shop with lateness penalties, Computers & Operations Research 23: 131–140.
Slotnick S.A., Morton T.E., 2007, Order acceptance with weighted tardiness, Computers & Operations Research 34: 3029–3042.
Sviridenko M. I.,2004, A note on permutation flow shop problem, Annals of Operations Research 129:247–252.
Torabzadeh E., Zandieh M., 2010, Cloud-theory based simulated annealing approach for scheduling in the two-stage assembly flow shop, Advances in Engineering Software 41:1238-1243.
Xiao Y.Y., 2012, Ren-Qian Zhang, Qiu-Hong Zhao, Ikou Kaku, Permutation flow shop scheduling with order acceptance and weighted tardiness, Applied Mathematics and Computation 218:7911-7926.
Yang B., Geunes J., 2007, A single resource scheduling problem with job-selection flexibility, tardiness costs and controllable processing times, Computers & Industrial Engineering 53:420–432.
Yingjun W., Zhongying Z., 2004, Pattern mining for time series based on cloud theory pan-concept-tree, International conference on rough sets and current trends in computing, 1:618–623.