Volume 3 Issue 3 pp. 313-320 Spring, 2012


Just-in-time preemptive single machine problem with costs of earliness/tardiness, interruption and work-in-process


Mohammad Kazemi, Elnaz Nikoofarid, Amin Aalaei and Reza Kia


This paper considers preemption and idle time are allowed in a single machine scheduling problem with just-in-time (JIT) approach. It incorporates Earliness/Tardiness (E/T) penalties, interruption penalties and holding cost of jobs which are waiting to be processed as work-in-process (WIP). Generally in non-preemptive problems, E/T penalties are a function of the completion time of the jobs. Then, we introduce a non-linear preemptive scheduling model where the earliness penalty depends on the starting time of a job. The model is liberalized by an elaborately–designed procedure to reach the optimum solution. To validate and verify the performance of proposed model, computational results are presented by solving a number of numerical examples.


DOI: 10.5267/j.ijiec.2011.11.004

Keywords: Just-in-time, Preemption, Earliness/Tardiness, Interruption Penalties, Work-In-Process, Single Machine Scheduling

References

Bector, C.R., Gupta, Y.P., & Gupta, M.C. (1988). Determination of an optimal common due date and optimal sequence in a single machine jobshop. International Journal of Production Research 26, 613–628.

Bülbül, K., Kaminsky, P., & Yano, C. (2007). Preemption in single machine earliness/tardiness scheduling. Journal of Scheduling 10, 271-292.

Davis, J.S., Kanet, J.J. (1993). Single-machine scheduling with early and tardy completion costs. Naval Research Logistics 40, 85-101.

Esteve, B., Aubijoux, C., Chartier, A., & T’kindt, V. (2006). A recovering beam search algorithm for the single machine Just-in-Time scheduling problem. European Journal of Operational Research 127, 798-813.

Garey, M.R., Tarjan, R.E., & Wilfong, G.T. (1988). One-processor scheduling with symmetric earliness and tardiness penalties. Mathematics of Operations Research 13, 330-348.

Gupta, J.N.D., & Chantaravarapan S. (2008). Single machine group scheduling with family setups to minimize total tardiness. International Journal of Production Research 46, 1707–1722.

Hendel, Y., Runge, N., & Sourd, F. (2009). The one-machine just-in-time scheduling problem with preemption. Discrete Optimization 6, 10-22.

Hendel, Y., & Sourd, F. (2005). The single machine just-in-time scheduling problem with preemptions. In: MISTA 2005: proceedings of the 2nd multidisciplinary international conference on scheduling: theory and applications. p. 140–8.

Hendel, Y., & Sourd, F. (2006). Efficient neighborhood search for the one-machine earliness/tardiness scheduling problem. European Journal of Operational Research 173, 108-119.

Hepdogan, S., Moraga, R., DePuy, G.W., & Whitehouse G.E. (2009). A meta-RaPS for the early/tardy single machine scheduling problem. International Journal of Production Research 47, 1717–1732.

Hoogeveen, J.A., & Van de Velde, S.L. (1996). A branch-and-bound algorithm for single-machine earliness/tardiness scheduling with idle time. INFORMS Journal on Computing 8, 402-412.

Khorshidian, H., Javadian, N., Zandieh, M., Rezaeian, J., & Rahmani, K. (2011). A genetic algorithm for JIT single machine scheduling with preemption and machine idle time. Expert Systems with Applications 38, 7911-7918.

Liao, C.-J., & Cheng, C.-C. (2007). A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date. Computers and Industrial Engineering 52, 404-413.

Luo, X., Chu, Ch., & Wang, Ch. (2006). Some dominance properties for single-machine tardiness problem with sequence-dependent setup times. International Journal of Production Research 44, 3367–3378.

M’Hallah, R. (2007). Minimizing total earliness and tardiness on a single machine using a hybrid heuristic. Computers & Operations Research 34, 3126-3142.

Nandkeolyar, U., Ahmed, M., & Sundararaghavan, P. (1993). Dynamic single-machine-weighted absolute deviation problem: predictive heuristics and evaluation. International Journal of Production Research 31(6), 1453–1466.

Runge, N., & Sourd, F. (2009). A new model for the preemptive earliness–tardiness scheduling problem. Computers & Operation Research, 36, 2242-2249.

Seidmann, A., Panwalkar, S.S., & Smith, M.L. (1981). Optimal assignment of due dates for a single processor scheduling problem. International Journal of Production Research 19, 393–399.

Shirazi, B., Fazlollahtabar, H., & Sahebjamnia, N. (2010). Minimizing arbitrary earliness/tardiness penalties with common due date in single-machine scheduling problem using a Tabu-Geno-Simulated Annealing. Materials and Manufacturing Processes 25, 515–525.

Sourd, F., & Kedad-Sidhoum, S. (2003). The one-machine scheduling with earliness and tardiness penalties. Journal of Scheduling 6, 533-549.

Sourd, F., & Kedad-Sidhoum, S. (2008). A faster branch-and-bound algorithm for the earliness_tardiness scheduling problem. Journal of Scheduling 11, 49-58.

Szwarc, W., & Mukhopadhyay, S.K. (1955). Optimal timing schedules in earliness/tardiness single machine sequencing. Naval Research Logistics 42, 1109-1114.

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.

Tavakkoli-Moghaddam, R., Moslehi, G., Vasei, M., & Azaron, A. (2006). A branch-and-bound algorithm for a single machine sequencing to minimize the sum of maximum earliness and tardiness with idle insert. Applied Mathematics and Computation 174, 388-408.

Ventura, J.A., & Weng, M.X. (1994). Single-machine scheduling for minimizing total cost with identical, asymmetrical earliness and tardiness penalties. International Journal of Production Research 32, 2725–2729.

Wan, G., & Yen, B.P.C. (2002). Tabu search for single machine with distinct due windows and weighted earliness/tardiness penalties. European Journal of Operational Research 142, 271-281.

Wan, G., & Yen, B.P.-C. (2009). Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs. European Journal of Operational Research 195, 89-97.