Bicriteria scheduling problem for unrelated parallel machines

https://doi.org/10.1016/0360-8352(95)00028-3Get rights and content

Abstract

In this paper scheduling of n jobs, all requiring a single stage of processing, on m unrelated parallel machines is considered. No preemption of jobs is allowed. There are two scheduling objectives, namely to minimize the makespan and to minimize the maximum tardiness. An algorithm based on tabu search is proposed for the above problem. Computational results are reported with data generated using various combinations of process time and due dates. Comparison is also made with a heuristic proposed earlier. The results show that the proposed algorithm gives better results both in terms of the quality of solution and execution time.

References (31)

  • H. Barron et al.

    Sensitivity analysis of multiattribute value models

    Ops. Res.

    (1988)
  • R.N. Burns

    Scheduling to minimize the weighted sum of completion time with secondary criteria

    NRLQ

    (1976)
  • J.L. Cohon

    Multiple Objective Programming and Planning

    (1978)
  • H. Emmons

    A note on a scheduling problem with dual criteria

    NRLQ

    (1975)
  • S. French

    Sequencing and Scheduling: Introduction to the Mathematics of the Job Shop

    (1982)
  • Cited by (45)

    • Single machine scheduling with two-agent for total weighted completion time objectives

      2018, Applied Soft Computing Journal
      Citation Excerpt :

      In the present paper, the objectives of two-agents are in conflict, because the completion time of jobs for the two agents are mutually independent. To address the conflicting nature of objective functions, Suresh and Chaudhuri [14] suggested to two approaches: (1) assign weight to the objective of each agent and minimize the weighted objective function; (2) minimize the objective function of one agent while keeping the objective function of the other agent within a pre-specified level. T. E. Cheng et al. [15] named these two types of single machine with multi-agent scheduling problem as a “minimality model” and a “feasibility model,” respectively.

    • A NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem

      2017, Computers and Industrial Engineering
      Citation Excerpt :

      Similarly, multiobjective PMS problems had been also widely studied in the literature and the most works focus on the technique of ‘posteriori’. Suresh and Chaudhuri (1996) proposed a TS based algorithm for a PMS problem with two objective functions of minimizing the makespan and the maximum tardiness. Cochran, Horng, and Fowler (2003) presented a two-stage multi-population GA for a PMS problem to minimize three different criteria that are the makespan, the total weighted tardiness and the total weighted completion time respectively.

    • Bicriteria scheduling problem for unrelated parallel machines with release dates

      2015, Computers and Operations Research
      Citation Excerpt :

      There is some research that uses genetic algorithm (GA)-based approaches to solve parallel machines with bicriteria objective scheduling problems [6,12,25,43], and some research that uses simulated annealing to solve parallel machines with bicriteria objective scheduling problems [17,37]. Additionally, there is some research that uses tabu searches to solve parallel machines with bicriteria objective scheduling problems [4,42]. In this research, we propose a bicriteria heuristic based on NEH [31] and apparent tardiness cost with release date (ATCR)[26] for the studied problem.

    • Non-permutation flowshop scheduling with dual resources Yasaman Mehravaran1

      2013, Expert Systems with Applications
      Citation Excerpt :

      There is a weight assigned to each job which shows the importance of those jobs in terms of WIP cost and service level. Most of the previous studies on scheduling problems with bicriteria goal (Chauhan, Gordon, & Proth, 2007; Chen & Vairaktarakis, 2005; Choua & Lee, 1999; Eren & Güner, 2006; Koksalan & Burak Keha, 2003; Mansouri, Hendizadeh, & Salmasi, 2009; Mehravaran & Logendran, 2011; Suresh & Chaudhuri, 1996) also attempt to consider the coordination of the producer and customers. In this research we tackled both objectives at the same time by using the traditional and the most common method of weighted aggregating function rather than the Pareto optimization.

    View all citing articles on Scopus

    Presently with Techno Economics Division, Kuwait Institute for Scientific Research, P.O. Box 24885, Safat 13109, Kuwait.

    View full text