Abstract
In this research, a bi-objective scheduling problem with controllable processing times on identical parallel machines is investigated. The direction of this paper is mainly motivated by the adoption of the just-in-time (JIT) philosophy on identical parallel machines in terms of bi-objective approach, where the job processing times are controllable. The aim of this study is to simultaneously minimize (1) total cost of tardiness, earliness as well as compression and expansion costs of job processing times and (2) maximum completion time or makespan. Also, the best possible set amount of compression/expansion of processing times on each machine is acquired via the proposed “bi-objective parallel net benefit compression-net benefit expansion” (BPNBC-NBE) heuristic. Besides that, a sequence of jobs on each machine, with capability of processing all jobs, is determined. In this area, no inserted idle time is allowed after starting machine processing. For solving such bi-objective problem, two multi-objective meta-heuristic algorithms, i.e., non-dominated sorting genetic algorithm II (NSGAII) and non-dominated ranking genetic algorithm (NRGA) are applied. Also, three measurement factors are then employed to evaluate the algorithms’ performance. Experimental results reveal that NRGA has better convergence near the true Pareto-optimal front as compared to NSGAII, while NSGAII finds a better spread in the entire Pareto-optimal region.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baker, K.R., 1994. Elements of sequencing and scheduling, Hanover: HN
Sun H, Wang G (2003) Parallel machine earliness and tardiness scheduling with proportional weights. Comput Oper Res 30(5):801–808
Hall NG, Posner ME (2001) Generating experimental date for computational testing with machine scheduling applications. Oper Res 49:854–865
Baker KR, Scudder GD (1990) Sequencing with earliness and tardiness penalties: a review. Oper Res 38:22–36
Hall NG, Posner ME (1991) Earliness–tardiness scheduling problems. I: weighted deviation of completion times about a common due date. Oper Res 39:836–846
Wang A, Huang Y, Taunk P, Magnin DR, Ghosh K, Robertson JG (2003) Application of robotics to steady state enzyme kinetics: analysis of tight-binding inhibitors of dipeptidyl peptidase IV. Anal Biochem 321(2):157–166
Sørensen, J.F., Kragh, K.M., Sibbesen, O., Delcour, J., Goesaert, H., Svensson, B., et al., 2004. Potential role of glycosidase inhibitors in industrial biotechnological applications. Biochimica et Biophysica Acta (BBA)-Proteins & amp; Proteomics 1696(2), 275–287
Sivrikaya F, Ulusoy G (1999) Parallel machine scheduling with earliness and tardiness penalties. Comput Oper Res 26:773–787
Cheng R, Gen M, Tosawa T (1995) Minmax earliness/tardiness scheduling in identical parallel machine system using genetic algorithms. Comput Ind Eng 29:513–517
Kedad-Sidhoum S, Solis YR, Sourd F (2008) Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates. Eur J Oper Res 189(3):1305–1316
Su LH (2009) Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system. Comput Oper Res 36(2):461–471
Drobouchevitch IG, Sidney JB (2012) Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs. Comput Oper Res 39(9):1919–1926
Biskup D, Herrmann J, Gupta JND (2008) Scheduling identical parallel machines to minimize total tardiness. Int J Prod Econ 115(1):134–142
Xi Y, Jang J (2012) Scheduling jobs on identical parallel machines with unequal future ready time and sequence dependent setup: an experimental study. Int J Prod Econ 137(1):1–10
Shmoys, D.B., Tardos, E., 1993. Scheduling unrelated machines with costs, In: Proceedings of the 4th Annual ACM-SIAM Symposium, Austin, TX, January 25–27, pp. 448–454
Coffman EG, Sethi R (1976) Algorithms minimizing mean flow time: schedule length properties. Acta Informatica 6:1–14
Lin CH, Liao CJ (2004) Makespan minimization subject to flowtime optimality on identical parallel machines. Comput Oper Res 31:1655–1666
Ruiz-Torres AJ, Lopez FJ (2004) Using the FDH formulation of DEA to evaluate a multi-criteria problem in parallel machine scheduling. Comput Ind Eng 47:107–121
Suresh V, Chaudhuri D (1996) Bicriteria scheduling problem for unrelated parallel machines. Comput Ind Eng 30:77–82
Ruiz-Torres AJ, Enscore EE, Barton RR (1997) Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problem. Comput Ind Eng 33:257–260
Chang PC, Chen SH, Lin KL (2005) Two-phase sub population genetic algorithm for parallel machine-scheduling problem. Expert Syst Appl 29:705–712
Gao J, He G, Wang Y (2009) A new parallel genetic algorithm for solving multi objective scheduling problems subjected to special process constraint. Int J Adv Manuf Technol 43:151–160
Gao J (2010) A novel artificial immune system for solving multiobjective scheduling problems subject to special process constraint. Comput Ind Eng 58:602–609
Tavakkoli-Moghaddam R, Taheri F, Bazzazi M, Izadi M, Sassani F (2009) Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Comput Oper Res 36(12):3224–3230
Radhakrishnan S, Ventura JA (2000) Simulated annealing for parallel machine scheduling with earliness/tardiness penalties and sequence-dependent setup times. Int J Prod Res 38(10):2233–2252
Vickson RG (1980) Two single machine sequencing problems involving controllable job processing times. AIIE Trans 12:258–262
Nowicki E, Zdrzalka S (1990) A survey of results for sequencing problems with controllable processing times. Discret Appl Math 26:271–287
Lee IS (1991) Single machine scheduling with controllable processing times: a parametric study. Int J Prod Econ 22(2):105–110
Liman S, Panwalkar S, Thongmee S (1997) A single machine scheduling problem with common due window and controllable processing times. Ann Oper Res 70:145–154
Shabtay D, Steiner G (2007) A survey of scheduling with controllable processing times. Discret Appl Math 155:1643–1666
Gurel S, Akturk MS (2007) Scheduling parallel CNC machines with time/cost trade-off considerations. Comput Oper Res 34(9):2774–2789
Alidaee B, Ahmadian A (1993) Two parallel machine sequencing problems involving controllable job processing times. Eur J Oper Res 70(3):335–341
Wan, G., 2007. Single machine common due window scheduling with controllable job processing times, combinatorial optimization and applications, A. Dress, Y. Xu, and B. Zhu, Editors. Springer Berlin Heidelberg. pp. 279–290
Shakhlevich N, Strusevich V (2008) Preemptive scheduling on uniform parallel machines with controllable job processing times. Algorithmica 51(4):451–473
Shabtay D (2010) Scheduling and due date assignment to minimize earliness, tardiness, holding, due date assignment and batch delivery costs. Int J Prod Econ 123(1):235–242
Aktürk M, Atamtürk A, Gürel S (2010) Parallel machine match-up scheduling with manufacturing cost considerations. J Sched 13(1):95–110
Leyvand Y, Shabtay D, Steiner G, Yedidsion L (2010) Just-in-time scheduling with controllable processing times on parallel machines. J Comb Optim 19(3):347–368
Yin N, Wang X-Y (2011) Single-machine scheduling with controllable processing times and learning effect. Int J Adv Manuf Technol 54(5–8):743–748
Li K, Shi Y, Yang S, Cheng BY (2011) Parallel machine scheduling problem to minimize the makespan with resource dependent processing times. Appl Soft Comput 11(8):5551–5557
Jansen K, Mastrolilli M (2004) Approximation schemes for parallel machine scheduling problems with controllable processing times. Comput Oper Res 31(10):1565–1581
Niu, G., Sun, S., Lafon, P., Zhang, Y., & Wang, J. (2012). Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times. International Journal of Production Research, 50(24):7415–7427
Renna P (2013) Controllable processing time policies for job shop manufacturing system. Int J Adv Manuf Technol 67(9–12):2127–2136
Low C, Li R-K, Wu G-H (2013) Ant colony optimization algorithms for unrelated parallel machine scheduling with controllable processing times and eligibility constraints. Proceedings of the Institute of Industrial Engineers Asian Conference 2013. Springer, Singapore, pp 79–87
Kayvanfar V, Mahdavi I, Komaki GM (2013) Single machine scheduling with controllable processing times to minimize total tardiness and earliness. Comput Ind Eng 65(1):166–175
Kayvanfar V, Mahdavi I, Komaki GM (2013) A drastic hybrid heuristic algorithm to approach to JIT policy considering controllable processing times. Int J Adv Manuf Technol 69:257–267
Kayvanfar V, Komaki GHM, Aalaei A, Zandieh M (2014) Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times. Comput Oper Res 41:31–43
Pinedo, M., 1995. Scheduling: theory, algorithms, and systems. Englewood Cli (s, NJ: Prentice-Hall
Hillier FS, Lieberman GJ (2001) Introduction to operations research, 7th edn. McGraw-Hill, New York
Anagnostopoulos KP, Mamanis G (2010) A portfolio optimization model with three objectives and discrete variables. Comput Oper Res 37(7):1285–1297
Zitzler, E., Laumanns, M., Thiele, L., 2001. SPEA2: Improving the strength Pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35: CH-8092 Zurich, Switzerland
Horn, J., Nafploitis, N., Goldberg, D.E., 1994. A niched Pareto genetic algorithm for multiobjective optimization. In: Proceeding of the first IEEE Conference on Evolutionary Computation, IEEE Press, pp. 82–87
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197
Al Jadaan O, Rajamani L, Rao CR (2008) Non-dominated ranked genetic algorithm for solving multi-objective optimisation problems: NRGA. J Theor Appl Inf Technol 2:60–67
Coello, C.C., Lamont, G.B., Veldhuizen, D.A., 2007. Evolutionary algorithms for solving multi-objective problems. 2nd ed. Springer
Deb K (2001) Multi objective optimization using evolutionary algorithms. Wiley, Chichester
Deb, K., Sachin, J., 2004. Running performance metrics for evolutionary multi-objective optimization. Kanpur Genetic Algorithm Laboratory (KanGAL), Report No.2002004
Zitzler, E., 1999. Evolutionary algorithms for multiobjective optimization: methods and applications. Ph.D. dissertation ETH 13398, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland
Schott, J.R., 1995. Fault tolerant design using single and multi-criteria genetic algorithms. Master’s Thesis, Boston MA: Department of Aeronautics and Astronautics, Massachusetts Institute of Technology
Deb K, Agarwal S, Pratap A, Meyarivan T (2000) Technical report 200001, Indian Institute of Technology. Kanpur Genetic Algorithms Laboratory (KanGAL), Kanpur, A fast and elitist multi objective genetic algorithm: NSGA-II
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zarandi, M.H.F., Kayvanfar, V. A bi-objective identical parallel machine scheduling problem with controllable processing times: a just-in-time approach. Int J Adv Manuf Technol 77, 545–563 (2015). https://doi.org/10.1007/s00170-014-6461-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-014-6461-8