AN INTEGRATED APPROACH FOR SINGLE MACHINE SCHEDULING WITH SEQUENCE-DEPENDENT SETUP TIMES
##plugins.themes.bootstrap3.article.main##
##plugins.themes.bootstrap3.article.sidebar##
Abstract
This study proposes a multi-choice goal programming for the single machine scheduling problem of minimizing the weighted number of tardy jobs, the total weighted completion time and makespan with sequence-dependent setup times. In this problem, there are n candidate jobs for processing in a single machine, each job has a weight, a due date, a processing time, and also sequence-dependent setup times exist between two consecutive jobs. In the first stage of the proposed methodology, the job weights of each job are determined by using the Analytic Hierarchy Process (AHP) method. In the second stage, a 0-1 mixed integer non-linear programming model is built by considering three objective functions and the ideal point is obtained by minimizing the objectives individually. Then, the multi-choice goal programming is used to allow the decision makers to set multi-choice aspiration levels for each goal.
http://dx.doi.org/10.13033/ijahp.v7i1.291
How to Cite
Downloads
##plugins.themes.bootstrap3.article.details##
AHP, single machine scheduling problem, sequence-dependent setup times, Multi-choice goal programming, 0-1 mixed integer non-linear programming model
involving setup considerations. Omega, 27, 219–39.
Arcelus, F.J., & Chandra, R. (1983). On n-1-F setup dependent problems. Engineering
Optimization, 7, 59–67.
Armentano, V.A., & Mazzini, R. (2000). A genetic algorithm for scheduling on a single
machine with set-up times and due dates. Production Planning and Control, 11, 713–720.
Asano, M., & Ohta, H. (1999). Scheduling with shutdowns and sequence dependent setup
times. International Journal of Production Research, 37, 1661–1676.
Bahalke, U., Yolmeh, A.M., & Shahanaghi, K. (2010). Meta-heuristics to solve singlemachine
scheduling problem with sequence-dependent setup time and deteriorating jobs,
International Journal of Advanced Manufacturing Technology, 50, 749-759.
Ben Mahmoud, H., Ketata, R., Ben Romdhane, T., & Ben Ahmed, S. (2010). Piloting a
quality management system for study case using multi-choice goal programming, in:
Conference Proceedings – IEEE International Conference on Systems, Man and
Cybernetics, 2010, article no. 5641929, 2500–2505.
Bianco, L., Mingozzi, A., & Ricciardelli, S. (1993). The travelling salesman problem
with cumulative costs. Networks, 23, 81–91.
Chang, T.Y., Chou, F.D. & Lee, C.E. (2004). A heuristic algorithm to minimize total
weighted tardiness on a single machine with release dates and sequence-dependent setup
times. Journal of the Chinese Institute of Industrial Engineers, 21, 289–300.
Chang, C.T. (2007). Multi-choice goal programming. Omega 35, 389–396.
Chang, C.T. (2008). Revised multi-choice goal programming. Applied Mathematical
Modeing, 32, 2587–2595.
Chen, C.L. (2012). Iterated hybrid metaheuristic algorithms for unrelated parallel
machines problem with unequal ready times and sequence-dependent setup times.
International Journal of Advanced Manufacturing Technology, 60, 693-705.
Chen, J.F. (2013). Unrelated parallel-machine scheduling to minimize total weighted
completion time. Journal of Intelligent Manufacturing, 1-14 (Article in Press).
Da Silva A.F., Marins F.A.S., & Montevechi J.A.B. (2013a). Multi-choice mixed integer
goal programming optimization for real problems in a sugar and ethanol milling
company. Applied Mathematical Modelling, 37(9), 6146–6162.
Da Silva A.F., Marins F.A.S., & Montevechi J.A.B. (2013b). Application of mixed
binary goal programming in an enterprise in the sugar and energy sector. Gestao e
Producao, 20(2), 321-335.
Di, L., & Ze, T. (2011). A genetic algorithm with Tabu Search for multi-objective
scheduling constrained flexible job shop, Proceedings of 2011 Cross Strait QuadRegional
Radio Science and Wireless Technology Conference, 1662-1665.
Eren, T., & Güner, E. (2006). A bicriteria scheduling with sequence-dependent setup
times. Applied Mathematics and Computation, 179, 378–385.
Fang, Y., Wang, F., & Wang, H. (2011). Research of multi-objective optimization study
for job shop scheduling problem based on grey ant colony algorithm. Advanced Materials
Research, 308-310, 1033-1036.
Fazlollahtabar, H., Mahdavi, I., Ashoori, M.T., Kaviani, S., & Mahdavi-Amiri, N. (2011).
A multi-objective decision-making process of supplier selection and order allocation for
multi-period scheduling in an electronic market. International Journal of Advanced
Manufacturing Technology, 52, 1039–1052
Fischetti, M., Laporte, G., & Martello, S. (1993). The delivery man problem and
cumulative matroids. Operations Research, 41, 1055–1064.
Franca, P.M., Mendes, A., & Moscato, P. (2001). A memetic algorithm for the total
tardiness single machine scheduling problem. European Journal of Operational
Research, 132, 224–242.
Gagne, C., Price, W.L., & Gravel, M. (2002). Comparing an ACO algorithm with other
heuristics for the single machine scheduling problem with sequence-dependent setup
times. Journal of the Operational Research Society, 53, 895–906.
Gupta, S.R., & Smith, J.S. (2006). Algorithms for single machine total tardiness
scheduling with sequence dependent setups. European Journal of Operational Research,
175, 722–739.
K?r??, ?., & Saraç, T. (2009). Modeling the fuzzy goal programming for scheduling
problem of single machine with sequence dependent set-up times. 1st International Fuzzy
Systems Symposium, Ankara, Turkey, 34-40.
Lee, S.M., & Asllani, A.A. (2004). Job scheduling with dual criteria and sequencedependent
setups: mathematical versus genetic programming. Omega, 32 (2), 145–153.
Lee, A.H.I., Kang, H.-Y., Yang, C.-Y., & Lin, C.-Y. (2010). An evaluation framework
for product planning using FANP, QFD and multi-choice goal programming.
International Journal of Production Research, 48(13), 3977–3997.
Liao, C.N., & Kao, H.P. (2010). Supplier selection model using Taguchi loss function,
analytical hierarchy process and multi-choice goal programming. Computers and
Industrial Engineering, 58, 571–577.
Lin, D., Lee, C.K.M., & Wu, Z. (2012). Integrating analytical hierarchy process to
genetic algorithm for re-entrant flow shop scheduling problem. International Journal of
Production Research, 50(7), 1813-1824.
Macharis, C., Springael, J., De Brucher, K., & Verbeke, A. (2004). PROMETHEE and
AHP: The design of operational synergies in multicriteria analysis. Strengthening
PROMETHEE with ideas of AHP, European Journal of Operational Research, 153(2),
307–317.
Mendes, A.S., Franca, P.M., & Moscato P. (2002). Fitness landscapes for the total
tardiness single machine scheduling problem. Neural Network World, 12,165–180.
Miyazaki, S., & Ohta H. (1987). Backward scheduling to minimize the actual mean flow
time with dependent and independent setup times. Proceedings of the. IXth ICPR, 2680–
2686.
Paksoy, T., & Chang, C.T. (2010). Revised multi-choice goal programming for multiperiod,
multi-stage inventory controlled supply chain model with popup stores in Guerilla
marketing. Applied Mathematical Modelling, 34, 3586–3598.
Pinedo M. (1995). Scheduling: theory, algorithms, and systems. Englewood, NJ:
Prentice-Hall, Inc.
Panwalker S.S., & Iskander, W. (1977). A survey of scheduling rule. Operations
Research, 25, 45–61.
Rabadi, G., Mollaghasemi, M., & Anagnostopoulos G.C. (2004). A branch and- bound
algorithm for the early/tardy machine scheduling problem with a common due-date and
sequence dependent setup time. Computers and Operations Research, 31, 1727–1751.
Romero, C. (2004). A general structure of achievement function for a goal programming
model. European Journal of Operational Research, 153, 675–686.
Saaty, T.L. (1980). The Analytic Hierarchy Process, New York: McGraw-Hill.
Saaty, T.L. (2000). Fundamentals of decision making and priority theory with the
Analytic Hierarchy Process. Pittsburgh, USA: RWS Publications.
Schrage, L. (2008). Optimization modeling with Lingo, Chicago: Lindo Systems Inc.
Shin, H.J., Kim, C.O., & Kim, S.S. (2002). A tabu search algorithm for single machine
scheduling with release times, due dates, and sequence-dependent set-up times.
International Journal of Advanced Manufacturing Technology, 19, 859–866.
Sioud, A., Gravel, M. & Gagné, C. (2012). A hybrid genetic algorithm for the single
machine scheduling problem with sequence-dependent setup times. Computers and
Operations Research, 39, 2415-2424.
Tan, K.C., & Narasimhan,R. (1997). Minimizing tardiness on a single processor with
sequence-dependent setup times: A simulated annealing approach. Omega, 25, 619–634.
Tan, K.C., Narasimhan, R., Rubin, P.A., & Ragatz, G.L. (2000). A comparison of four
methods for minimizing total tardiness on a single processor with sequence dependent
setup times. Omega, 28, 313–326.
Ustun, O. (2012). Multi-choice goal programming formulation based on the conic
scalarizing function. Applied Mathematical Modelling, 36, 974–988.
Wang, L., & Wang, M. (1997). Hybrid algorithm for earliness–tardiness scheduling
problem with sequence dependent setup time, Proceedings of the IEEE Conference on
Decision and Control 2, 1219–1222.
Witkowski, T., Antczak, P., & Antczak, A. (2009). Multi-objective decision making and
search space for the evaluation of production process scheduling, Bulletin of the Polish
Academy of Sciences: Technical Sciences, 57(3), 195-208.
Wu, X., Sun, S., Yu, J., & Cai, Z. (2007). A multi -objective scheduling decision making
model for the flexible job shop. Zhongguo Jixie Gongcheng/China Mechanical
Engineering, 18(2), 161-165.
Copyright of all articles published in IJAHP is transferred to Creative Decisions Foundation (CDF). However, the author(s) reserve the following:
- All proprietary rights other than copyright, such as patent rights.
- The right to grant or refuse permission to third parties to republish all or part of the article or translations thereof. In case of whole articles, such third parties must obtain permission from CDF as well. However, CDF may grant rights with respect to journal issues as a whole.
- The right to use all or parts of this article in future works of their own, such as lectures, press releases, reviews, textbooks, or reprint books.
- The authors affirm that the article has been neither copyrighted nor published, that it is not being submitted for publication elsewhere, and that if the work is officially sponsored, it has been released for open publication.
The only exception to the statements in the paragraph above is the following: If an article published in IJAHP contains copyrighted material, such as a teaching case, as an appendix, then the copyright (and all commercial rights) of such material remains with the original copyright holder.
CDF will receive permission for publication of copyrighted material in IJAHP. This permission is not transferable to third parties. Permission to make electronic and paper copies of part or all of the articles, including all computer files that are linked to the articles, for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage.
This permission does not apply to previously copyrighted material, such as teaching cases. In paper copies of the article, the copyright notice and the title of the publication and its date should be visible. To copy otherwise is permitted provided that a per-copy fee is paid.
To republish, to post on servers, or redistribute to lists requires that you post a link to the IJAHP article, which is available in open access delivery mode. Do not upload the article itself.
Authors are permitted to present a talk, based on a paper submitted to or accepted by IJAHP, at a conference where the paper would not be published in a copyrighted publication either before or after the conference and where the author did not assign copyright to the conference or related publisher.