{"title":"Solving Process Planning, Weighted Earliest Due Date Scheduling and Weighted Due Date Assignment Using Simulated Annealing and Evolutionary Strategies","authors":"Halil Ibrahim Demir, Abdullah Hulusi Kokcam, Fuat Simsir, \u00d6zer Uygun","volume":129,"journal":"International Journal of Industrial and Manufacturing Engineering","pagesStart":1547,"pagesEnd":1555,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/10007844","abstract":"
Traditionally, three important manufacturing functions which are process planning, scheduling and due-date assignment are performed sequentially and separately. Although there are numerous works on the integration of process planning and scheduling and plenty of works focusing on scheduling with due date assignment, there are only a few works on integrated process planning, scheduling and due-date assignment. Although due-dates are determined without taking into account of weights of the customers in the literature, here weighted due-date assignment is employed to get better performance. Jobs are scheduled according to weighted earliest due date dispatching rule and due dates are determined according to some popular due date assignment methods by taking into account of the weights of each job. Simulated Annealing, Evolutionary Strategies, Random Search, hybrid of Random Search and Simulated Annealing, and hybrid of Random Search and Evolutionary Strategies, are applied as solution techniques. Three important manufacturing functions are integrated step-by-step and higher integration levels are found better. Search meta-heuristics are found to be very useful while improving performance measure.<\/p>\r\n","references":"[1]\tH.-C. Zhang and S. Mallur, \u201cAn integrated model of process planning and production scheduling,\u201d Int. J. Comput. Integr. Manuf., vol. 7, no. 6, pp. 356\u2013364, Nov. 1994.\r\n[2]\tV. Gordon, J.-M. Proth, and C. Chu, \u201cA survey of the state-of-the-art of common due date assignment and scheduling research,\u201d Eur. J. Oper. Res., vol. 139, no. 1, pp. 1\u201325, May 2002.\r\n[3]\tW. Tan and B. Khoshnevis, \u201cIntegration of process planning and scheduling\u2014 a review,\u201d J. Intell. Manuf., vol. 11, no. 1, pp. 51\u201363, Feb. 2000.\r\n[4]\tJ. M. Usher, \u201cEvaluating the impact of alternative plans on manufacturing performance,\u201d Comput. Ind. Eng., vol. 45, no. 4, pp. 585\u2013596, Dec. 2003.\r\n[5]\tK. Bhaskaran, \u201cProcess plan selection,\u201d Int. J. Prod. Res., vol. 28, no. 8, pp. 1527\u20131539, 1990.\r\n[6]\tN. Morad and A. Zalzala, \u201cGenetic algorithms in integrated process planning and scheduling,\u201d J. Intell. Manuf., vol. 10, no. 2, pp. 169\u2013179, Apr. 1999.\r\n[7]\tH. Lee and S.-S. Kim, \u201cIntegration of Process Planning and Scheduling Using Simulation Based Genetic Algorithms,\u201d Int. J. Adv. Manuf. Technol., vol. 18, no. 8, pp. 586\u2013590, Oct. 2001.\r\n[8]\tC. Moon, J. Kim, and S. Hur, \u201cIntegrated process planning and scheduling with minimizing total tardiness in multi-plants supply chain,\u201d Comput. Ind. Eng., vol. 43, no. 1\u20132, pp. 331\u2013349, Jul. 2002.\r\n[9]\tY. K. Kim, K. Park, and J. Ko, \u201cA symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling,\u201d Comput. Oper. Res., vol. 30, no. 8, pp. 1151\u20131171, Jul. 2003.\r\n[10]\tI. Drstven\u0161ek and J. Bali\u010d, \u201cResponding ability in dynamic production circumstances,\u201d J. Mater. Process. Technol., vol. 133, no. 1, pp. 71\u201378, 2003.\r\n[11]\tC. Moon, Y. H. Lee, C. S. Jeong, and Y. Yun, \u201cIntegrated process planning and scheduling in a supply chain,\u201d Comput. Ind. Eng., vol. 54, no. 4, pp. 1048\u20131061, May 2008.\r\n[12]\tX. Li, C. Zhang, L. Gao, W. Li, and X. Shao, \u201cAn agent-based approach for integrated process planning and scheduling,\u201d Expert Syst. Appl., vol. 37, no. 2, pp. 1256\u20131264, Mar. 2010.\r\n[13]\tA. Seker, S. Erol, and R. Botsali, \u201cA neuro-fuzzy model for a new hybrid integrated Process Planning and Scheduling system,\u201d Expert Syst. Appl., vol. 40, no. 13, pp. 5341\u20135351, Oct. 2013.\r\n[14]\tL. Zhang and T. N. Wong, \u201cAn object-coding genetic algorithm for integrated process planning and scheduling,\u201d Eur. J. Oper. Res., vol. 244, no. 2, pp. 434\u2013444, Jul. 2015.\r\n[15]\tR. Meenakshi Sundaram and S. Fu, \u201cProcess planning and scheduling \u2014 A method of integration for productivity improvement,\u201d Comput. Ind. Eng., vol. 15, no. 1\u20134, pp. 296\u2013301, 1988.\r\n[16]\tN. Nasr and E. A. Elsayed, \u201cJob shop scheduling with alternative machines,\u201d Int. J. Prod. Res., vol. 28, no. 9, pp. 1595\u20131609, Sep. 1990.\r\n[17]\tB. Khoshnevis and Q. M. Chen, \u201cIntegration of process planning and scheduling functions,\u201d J. Intell. Manuf., vol. 2, no. 3, pp. 165\u2013175, Jun. 1991.\r\n[18]\tJ. Hutchison, K. Leong, D. Synder, and P. Ward, \u201cScheduling approaches for random job shop flexible manufacturing systems,\u201d Int. J. Prod. Res., vol. 29, no. 5, pp. 1053\u20131067, May 1991.\r\n[19]\tJ. M. Usher and K. J. Fernandes, \u201cDynamic process planning\u2014the static phase,\u201d J. Mater. Process. Technol., vol. 61, no. 1\u20132, pp. 53\u201358, 1996.\r\n[20]\tP. Brandimarte, \u201cExploiting process plan flexibility in production scheduling: A multi-objective approach,\u201d Eur. J. Oper. Res., vol. 114, no. 1, pp. 59\u201371, Apr. 1999.\r\n[21]\tK.-H. Kim and P. J. Egbelu, \u201cScheduling in a production environment with multiple process plans per job,\u201d Int. J. Prod. Res., vol. 37, no. 12, pp. 2725\u20132753, Aug. 1999.\r\n[22]\tA. Weintraub, D. Cormier, T. Hodgson, R. King, J. WIlson, and A. Zozom, \u201cScheduling with alternatives: a link between process planning and scheduling,\u201d IIE Trans., vol. 31, no. 11, pp. 1093\u20131102, Nov. 1999.\r\n[23]\tC. Saygin, F. F. Chen, and J. Singh, \u201cReal-time manipulation of alternative routeings in flexible manufacturing systems: a simulation study,\u201d Int. J. Adv. Manuf. Technol., vol. 18, no. 10, pp. 755\u2013763, 2001.\r\n[24]\tC. S. Thomalla, \u201cJob shop scheduling with alternative process plans,\u201d Int. J. Prod. Econ., vol. 74, no. 1\u20133, pp. 125\u2013134, Dec. 2001.\r\n[25]\tJ. Zhang, L. Gao, F. T. S. Chan, and P. Li, \u201cA holonic architecture of the concurrent integrated process planning system,\u201d J. Mater. Process. Technol., vol. 139, no. 1\u20133, pp. 267\u2013272, Aug. 2003.\r\n[26]\tC. Moon and Y. Seo, \u201cEvolutionary algorithm for advanced process planning and scheduling in a multi-plant,\u201d Comput. Ind. Eng., vol. 48, no. 2, pp. 311\u2013325, Mar. 2005.\r\n[27]\tX. Shao, X. Li, L. Gao, and C. Zhang, \u201cIntegration of process planning and scheduling\u2014A modified genetic algorithm-based approach,\u201d Comput. Oper. Res., vol. 36, no. 6, pp. 2082\u20132096, Jun. 2009.\r\n[28]\tC. \u00d6zg\u00fcven, L. \u00d6zbak\u0131r, and Y. Yavuz, \u201cMathematical models for job-shop scheduling problems with routing and process plan flexibility,\u201d Appl. Math. Model., vol. 34, no. 6, pp. 1539\u20131548, Jun. 2010.\r\n[29]\tX. Li, X. Shao, L. Gao, and W. Qian, \u201cAn effective hybrid algorithm for integrated process planning and scheduling,\u201d Int. J. Prod. Econ., vol. 126, no. 2, pp. 289\u2013298, Aug. 2010.\r\n[30]\tR. K. Phanden, A. Jain, and R. Verma, \u201cIntegration of process planning and scheduling: a state-of-the-art review,\u201d Int. J. Comput. Integr. Manuf., vol. 24, no. 6, pp. 517\u2013534, Jun. 2011.\r\n[31]\tX. Li, L. Gao, and W. Li, \u201cApplication of game theory based hybrid algorithm for multi-objective integrated process planning and scheduling,\u201d Expert Syst. Appl., vol. 39, no. 1, pp. 288\u2013297, Jan. 2012.\r\n[32]\tC. Dewu, S. Li, and T. Guochun, \u201cSingle machine scheduling with common due date assignment in a group technology environment,\u201d Math. Comput. Model., vol. 25, no. 3, pp. 81\u201390, 1997.\r\n[33]\tM. Y. Kovalyov, \u201cBatch scheduling and common due date assignment problem: an NP-hard case,\u201d Discrete Appl. Math., vol. 80, no. 2\u20133, pp. 251\u2013254, 1997.\r\n[34]\tD. Biskup and H. Jahnke, \u201cCommon due date assignment for scheduling on a single machine with jointly reducible processing times,\u201d Int. J. Prod. Econ., vol. 69, no. 3, pp. 317\u2013322, Feb. 2001.\r\n[35]\tT. C. E. Cheng, Z.-L. Chen, and N. V. Shakhlevich, \u201cCommon due date assignment and scheduling with ready times,\u201d Comput. Oper. Res., vol. 29, no. 14, pp. 1957\u20131967, Dec. 2002.\r\n[36]\tV. Lauff and F. Werner, \u201cScheduling with common due date, earliness and tardiness penalties for multimachine problems: A survey,\u201d Math. Comput. Model., vol. 40, no. 5\u20136, pp. 637\u2013655, Sep. 2004.\r\n[37]\tV. S. Gordon and V. A. Strusevich, \u201cSingle machine scheduling and due date assignment with positionally dependent processing times,\u201d Eur. J. Oper. Res., vol. 198, no. 1, pp. 57\u201362, Oct. 2009.\r\n[38]\tH. Allaoua and I. Osmane, \u201cVariable Parameters Lengths Genetic Algorithm for Minimizing Earliness-Tardiness Penalties of Single Machine Scheduling With a Common Due Date,\u201d Electron. Notes Discrete Math., vol. 36, pp. 471\u2013478, Aug. 2010.\r\n[39]\tN. H. Tuong and A. Soukhal, \u201cDue dates assignment and JIT scheduling with equal-size jobs,\u201d Eur. J. Oper. Res., vol. 205, no. 2, pp. 280\u2013289, Sep. 2010.\r\n[40]\tY. Yin, T. C. E. Cheng, D. Xu, and C.-C. Wu, \u201cCommon due date assignment and scheduling with a rate-modifying activity to minimize the due date, earliness, tardiness, holding, and batch delivery cost,\u201d Comput. Ind. Eng., vol. 63, no. 1, pp. 223\u2013234, Aug. 2012.\r\n[41]\tH. Luss and M. B. Rosenwein, \u201cA due date assignment algorithm for multiproduct manufacturing facilities,\u201d Eur. J. Oper. Res., vol. 65, no. 2, pp. 187\u2013198, 1993.\r\n[42]\tV. Gordon and W. Kubiak, \u201cSingle machine scheduling with release and due date assignment to minimize the weighted number of late jobs,\u201d Inf. Process. Lett., vol. 68, no. 3, pp. 153\u2013159, Nov. 1998.\r\n[43]\tT. C. E. Cheng and M. Y. Kovalyov, \u201cComplexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness,\u201d Eur. J. Oper. Res., vol. 114, no. 2, pp. 403\u2013410, Apr. 1999.\r\n[44]\tV. S. Gordon and V. A. Strusevich, \u201cEarliness penalties on a single machine subject to precedence constraints: SLK due date assignment,\u201d Comput. Oper. Res., vol. 26, no. 2, pp. 157\u2013177, 1999.\r\n[45]\tA. Baykaso\u011flu, M. G\u00f6\u00e7ken, and Z. D. Unutmaz, \u201cNew approaches to due date assignment in job shops,\u201d Eur. J. Oper. Res., vol. 187, no. 1, pp. 31\u201345, May 2008.\r\n[46]\tY. Xia, B. Chen, and J. Yue, \u201cJob sequencing and due date assignment in a single machine shop with uncertain processing times,\u201d Eur. J. Oper. Res., vol. 184, no. 1, pp. 63\u201375, Jan. 2008.\r\n[47]\tS. Li, C. T. Ng, and J. Yuan, \u201cScheduling deteriorating jobs with CON\/SLK due date assignment on a single machine,\u201d Int. J. Prod. Econ., vol. 131, no. 2, pp. 747\u2013751, Jun. 2011.\r\n[48]\tX. Cai, V. Y. S. Lum, and J. M. T. Chan, \u201cScheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties,\u201d Eur. J. Oper. Res., vol. 98, no. 1, pp. 154\u2013168, 1997.\r\n[49]\tM. Birman and G. Mosheiov, \u201cA note on a due-date assignment on a two-machine flow-shop,\u201d Comput. Oper. Res., vol. 31, no. 3, pp. 473\u2013480, Mar. 2004.\r\n[50]\tL. Min and W. Cheng, \u201cGenetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness\/tardiness scheduling problems,\u201d Robot. Comput.-Integr. Manuf., vol. 22, no. 4, pp. 279\u2013287, Aug. 2006.\r\n[51]\tT. Yang, Z. He, and K. K. Cho, \u201cAn effective heuristic method for generalized job shop scheduling with due dates,\u201d Comput. Ind. Eng., vol. 26, no. 4, pp. 647\u2013660, 1994.\r\n[52]\tV. Vinod and R. Sridharan, \u201cSimulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system,\u201d Int. J. Prod. Econ., vol. 129, no. 1, pp. 127\u2013146, Jan. 2011.\r\n[53]\tS. R. Lawrence, \u201cNegotiating due-dates between customers and producers,\u201d Int. J. Prod. Econ., vol. 37, no. 1, pp. 127\u2013138, 1994.\r\n[54]\tJ. N. Gupta, K. Kr\u00fcger, V. Lauff, F. Werner, and Y. N. Sotskov, \u201cHeuristics for hybrid flow shops with controllable processing times and assignable due dates,\u201d Comput. Oper. Res., vol. 29, no. 10, pp. 1417\u20131439, 2002.\r\n[55]\tH. I. Demir, T. Cakar, M. Ipek, O. Uygun, and M. Sari, \u201cProcess Planning and Due-date Assignment with ATC Dispatching where Earliness, Tardiness and Due-dates are Punished,\u201d J. Ind. Intell. Inf. Vol, vol. 3, no. 3, 2015.\r\n[56]\tH. I. Demir and H. Taskin, \u201cIntegrated Process Planning, Scheduling and Due-Date Assignment,\u201d PhD Thesis, Sakarya University, 2005.\r\n[57]\tE. Ceven and H. I. Demir, \u201cBenefits of Integrating Due-Date Assignment with Process Planning and Scheduling,\u201d Master of Science Thesis, Sakarya University, 2007.\r\n[58]\tH. I. Demir, O. Uygun, I. Cil, M. Ipek, and M. Sari, \u201cProcess Planning and Scheduling with SLK Due-Date Assignment where Earliness, Tardiness and Due-Dates are Punished,\u201d J. Ind. Intell. Inf. Vol, vol. 3, no. 3, 2015.\r\n[59]\tS. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, and others, \u201cOptimization by simmulated annealing,\u201d science, vol. 220, no. 4598, pp. 671\u2013680, 1983.\r\n[60]\tI. Rechenberg, Cybernetic solution path of an experimental problem, vol. 1122. Ministry of Aviation, Royal Aircraft Establishment, Library Translation, 1965.\r\n[61]\tH.-P. Schwefel, Numerical optimization of computer models. John Wiley & Sons, Inc., 1981.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 129, 2017"}