A Possibility Linear Programming Approach to Solve a Fuzzy Single Machine Scheduling Problem

Document Type : Research Paper

Authors

1 1Department of Industrial Engineering, Faculty of Engineering, University of Kurdistan, Sanandaj, Iran

2 Department of Industrial Engineering, Faculty of Engineering, Tarbiat Modares University

3 Department of Industrial Engineering, Mazandaran University of Science and Technology

Abstract

This paper employs an interactive possibility linear programming approach to solve a single machine scheduling problem with imprecise processing times, due dates, as well as earliness and tardiness penalties of jobs. The proposed approach is based on a strategy of minimizing the most possible value of the imprecise total costs, maximizing the possibility of obtaining a lower total costs, and minimizing the risk of obtaining higher total costs simultaneously. This approach is applicable to just-in-time systems, in which many firms face the need to complete jobs as close as possible to their due dates. The objective of the model is to minimize the total costs of earliness/tardiness penalties. In this paper, the proposed possibility linear programming approach is applied to a fuzzy single machine scheduling problem with respect to the overall degree of decision maker satisfaction. Due to the proposed model’s complexity, conventional optimization methods cannot be utilized in reasonable time. Hence, the particle swarm optimization method is applied toward its solution.

Keywords

Main Subjects

References

[1] Bellman R. E., Zadeh L. A. (1970), Decision-making in a fuzzy environment; Management Science 17;
141-164.
[2] Brucker P. (1998), Scheduling Algorithms; Springer, Berlin.
[3] 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 14; 377-386.
[4] Chanas S., Kasperski A. (2003), On two single machine scheduling problems with fuzzy processing
times and fuzzy due dates; European Journal of Operational Research 147; 281-296.
[5] Chang P. C. (1999), Branch and bound approach for single machine scheduling with earliness and
tardiness penalties; Computers and Mathematics with Applications 37; 133-144.
[6] Chou F. D., Chang T. Y., Lee C. E. (2005), A heuristic algorithm to minimize total weighted tardiness
on a single machine with release times; International Transactions in Operations Research 12; 215-
233.
[7] Feldmann M., Biskup D. (2003), Single-machine scheduling for minimizing earliness and tardiness
penalties by meta-heuristic approaches; Computers and Industrial Engineering 44; 307-323.
[8] Hannan E. L. (1981), Linear programming with multiple fuzzy goals; Fuzzy Sets and Systems 6; 235-
248.
[9] Hu X., Shi Y., Eberhart R. (2004), Recent advances in particle swarm; in: Proceedings of 2004
Congress on Evolutionary Computation (CEC 2004), Portland, Oregon, Vol. 1, 90-97.
[10] Hwang C. L., Yoon K. (1981), Multiple attribute decision making: methods and applications; Springer,
Berlin.
[11] Kennedy J., Eberhart R. (1995), Particle swarm optimization. Proceedings of the IEEE International
Conference on Neural Networks (Perth, Australia), 1942–1948. Piscataway, NJ: IEEE Service Center.
[12] Lam S. S., Cai X. (2002), Single machine scheduling with nonlinear lateness cost functions and fuzzy
due dates; Nonlinear Analysis: Real World Applications 3; 307-316.
[13] Lai Y. J., Hwang C. L. (1992), A new approach to some possibility linear programming problems;
Fuzzy Sets and Systems 117; 35-45.
[14] Liaw C F (1999), A branch-and-bound algorithm for the single machine earliness and tardiness
scheduling problem; Computers and Operations Research 26; 679-693.
[15] Lin S.W., Chou S.Y., Ying K.C. (2006), A sequential exchange approach for minimizing earlinesstardiness
penalties of single-machine scheduling with a common due date; European Journal of
Operational Research Article in Press.
[16] Loukil T., Teghem J., Tuyttens D. (2005), Solving multi-objective production scheduling problems
using metaheuristics; European Journal of Operational Research 161; 42-61.
[17] Mazzini R., Armentano V. A. (2001), A heuristic for single machine scheduling with early and tardy
costs; European Journal of Operational Research 128; 129-146.
[18] Mondal S. A., Sen A. K. (2001), Single machine weighted earliness/tardiness penalty problem with a
common due date; Computers and Operations Research 28; 649-669.
[19] Peng J., Liu B. (2004), Parallel machine scheduling models with fuzzy processing times; Information
Sciences 166; 49-66.
[20] Rabadia 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.
[21] Shi Y., Eberhart R. (1998), A modified particle swarm optimizer. Proceedings of the IEEE
international conference on evolutionary computation. Piscataway, NJ: IEEE Press; 69–73.
[22] Tavakkoli-Moghaddam R., Moslehi G., Vasei M., Azaron A. (2005), Optimal scheduling for a single
machine to minimize the sum of maximum earliness and tardiness considering idle insert; Applied
Mathematics and Computation 167; 1430-1450.
[23] Ventura J. A., Radhakrishnan S. (2003), Single machine scheduling with symmetric earliness and
tardiness penalties; European Journal of Operational Research 144; 598-612.
[24] Wan G., Yen B. P. C. (2002), Tabu search for single machine scheduling with distinct due windows
and weighted earliness/tardiness penalties; European Journal of Operational Research 142; 271-281.
[25] Zimmermann H. J. (1978), Fuzzy programming and linear programming with several objective
functions, Fuzzy Sets and Systems 1; 45-56.
Journal of Industrial and Systems Engineering
Volume 1, Issue 2 - Serial Number 2
September 2007
Pages 116-129

Files

History

  • Receive Date: 11 January 2006
  • Revise Date: 27 April 2007
  • Accept Date: 27 May 2007

Share

How to cite

Statistics