Abstract
This study examines parallel machine scheduling problems with controllable processing times. The processing time of each job can be between lower and upper bounds, and a cost is associated with the processing of a job on a machine. The processing time of a job can be decreased, which may lower the cycle time, although doing so would incur additional costs. This study develops two multi-objective mathematical models, which consist of two and three inconsistent objective functions, respectively. The first model minimizes the total manufacturing cost (TMC) and the total weighted tardiness (TWT) simultaneously, while the second uses makespan (C max) as an additional objective function. In contrast to conventional mathematical models, efficient solutions are attained using the lexicographic weighted Tchebycheff method (LWT). Experimental results indicate that the LWT yields better-spread solutions and obtains more non-dominated solutions than its alternative, that is the weighted-sum method, which is a widely used yet promising approach to achieve multi-objective optimization. Results of this study also demonstrate that in purchasing machines, the variation in the fixed costs associated with the processing of jobs on machines is critical to reducing TWT. Moreover, using C max as an additional objective function typically improves TWT and worsens TMC.
Similar content being viewed by others
References
Aktürk MS, Atamtürk A and Gürel S (2010). Parallel machine match-up scheduling with manufacturing cost considerations. Journal of Scheduling 13 (1): 95–110.
Alidaee B and Ahmadian A (1993). Two parallel machine sequencing problems involving controllable job processing times. European Journal of Operational Research 70 (3): 335–341.
Cao D, Chen M and Wan G (2005). Parallel machine selection and job scheduling to minimize machine cost and job tardiness. Computers & Operations Research 32 (8): 1995–2012.
Deb K, Pratap A, Agarwal S and Meyarivan T (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6 (2): 182–197.
Fang K-T and Lin BMT (2013). Parallel-machine scheduling to minimize tardiness penalty and power cost. Computers & Industrial Engineering 64 (1): 224–234.
Gharehgozli AH, Tavakkoli-Moghaddam R and Zaerpour N (2009). A fuzzy-mixed-integer goal programming model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates. Robotics and Computer-Integrated Manufacturing 25 (4–5): 853–859.
Graham RL, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5: 287–326.
Gurel S and Akturk MS (2007). Scheduling parallel CNC machines with time/cost trade-off considerations. Computers & Operations Research 34 (9): 2774–2789.
Gürel S, Körpeoğlu E and Aktürk MS (2010). An anticipative scheduling approach with controllable processing times. Computers & Operations Research 37 (6): 1002–1013.
Huang B, Fery P, Xue L and Wang Y (2008). Seeking the Pareto front for multiobjective spatial optimization problems. International Journal of Geographical Information Science 22 (5): 507–526.
Jansen K and Mastrolilli M (2004). Approximation schemes for parallel machine scheduling problems with controllable processing times. Computers & Operations Research 31 (10): 1565–1581.
Kayvanfar V, Komaki GHM, Aalaei A and Zandieh M (2014). Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times. Computers & Operations Research 41: 31–43.
Kim IY and de Weck OL (2005). Adaptive weighted-sum method for bi-objective optimization: Pareto front generation. Structural and Multidisciplinary Optimization 29 (2): 149–158.
Lawler EL (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics 1: 331–342.
Leyvand Y, Shabtay D, Steiner G and Yedidsion L (2010). Just-in-time scheduling with controllable processing times on parallel machines. Journal of Combinatorial Optimization 19 (3): 347–368.
Li K, Shi Y, Yang S-L and Cheng B-Y (2011). Parallel machine scheduling problem to minimize the makespan with resource dependent processing times. Applied Soft Computing 11 (8): 5551–5557.
Mazdeh MM, Zaerpour F, Zareei A and Hajinezhad A (2010). Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs. Applied Mathematical Modelling 34 (6): 1498–1510.
Nowicki E and Zdrzałka S (1995). A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times. Discrete Applied Mathematics 63 (3): 237–256.
Pfund M, Fowler JW, Gadkari A and Chen Y (2008). Scheduling jobs on parallel machines with setup times and ready times. Computers & Industrial Engineering 54 (4): 764–782.
Samanlioglu F (2013). A multi-objective mathematical model for the industrial hazardous waste location-routing problem. European Journal of Operational Research 226 (2): 332–340.
Shabtay D and Steiner G (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics 155 (13): 1643–1666.
Steuer RE (1986). Multiple Criteria Optimization: Theory, Computation, and Application. New York: John Wiley & Sons.
Steuer RE and Choo E-U (1983). An interactive weighted Tchebycheff procedure for multiple objective programming. Mathematical Programming 26 (3): 326–344.
Tind J and Wiecek MM (1999). Augmented Lagrangian and Tchebycheff approaches in multiple objective programming. Journal of Global Optimization 14 (3): 251–266.
Tseng C-T, Liao C-J and Huang K-L (2009). Minimizing total tardiness on a single machine with controllable processing times. Computers & Operations Research 36 (6): 1852–1858.
Van Wassenhove LN and Baker KR (1982). A bicriterion approach to time/cost trade-offs in sequencing. European Journal of Operational Research 11 (1): 48–52.
Vickson RG (1980). Two single machine sequencing problems involving contollable job processing times. IIE Transactions 12 (3): 258–262.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, CH., Tsai, WN. Multi-objective parallel machine scheduling problems by considering controllable processing times. J Oper Res Soc 67, 654–663 (2016). https://doi.org/10.1057/jors.2015.82
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2015.82