Common Due-Date Assignment and Scheduling on Parallel Machines with Sequence-Dependent Setup Times

Jun-Gyu Kim; Jae-Min Yu; Dong-Ho Lee
May 2013
Management Science & Financial Engineering;May2013, Vol. 19 Issue 1, p29
Academic Journal
This paper considers common due-date assignment and scheduling on parallel machines. The main decisions are: (a) deter-mining the common due-date; (b) allocating jobs to machines; and (c) sequencing the jobs assigned to each machine. The objective is to minimize the sum of the penalties associated with common due-date assignment, earliness and tardiness. As an extension of the existing studies on the problem, we consider sequence-dependent setup times that depend on the type of job just completed and on the job to be processed. The sequence-dependent setups, commonly found in various manufacturing systems, make the problem much more complicated. To represent the problem more clearly, a mixed integer programming model is suggested, and due to the complexity of the problem, two heuristics, one with individual sequence-dependent setup times and the other with aggregated sequence-dependent setup times, are suggested after analyzing the characteristics of the problem. Computational experiments were done on a number of test instances and the results are reported.


Related Articles

  • A two-stage parallel branch and bound algorithm for mixed integer programs. Nwana, V.; Darby-Dowman, K.; Mitra, G. // IMA Journal of Management Mathematics;Jul2004, Vol. 15 Issue 3, p227 

    Mixed integer programming (MIP) models are extensively used to aid strategic and tactical decision making in many business sectors. Solving MIP models is a computationally intensive process and there is a need to develop solution approaches that enable larger models to be solved within...

  • GRADE SELECTION AND BLENDING TO OPTIMIZE COST AND QUALITY. Karmarkar, Uday S.; Rajaram, Kumar // Operations Research;Mar/Apr2001, Vol. 49 Issue 2, p271 

    In many chemical process applications, a large mix of products is produced by blending them from a much smaller set of basic grades. The basic grades themselves are typically produced on the same process equipment and inventoried in batches. Decisions that arise in this process include selecting...

  • A Variable Capacity Parallel Machine Scheduling Problem. Akyol, Emine; Saraç, Tugba // Proceedings of the International Conference on Industrial Engine;2012, p548 

    Parallel machine scheduling problem is significant because it is a common phenomenon in real life and a sub-problem of multi-stage complex problems. Studies about parallel machine scheduling usually analyzes a single planning period in which all the machines are active in all periods. However,...

  • ASSEMBLY LINE BALANCING WITH PROCESSING ALTERNATIVES: AN APPLICATION. Pinto, Peter A.; Dannenbring, David G.; Khumawala, Basheer M. // Management Science;Jul1983, Vol. 29 Issue 7, p817 

    The conventional approach to the assembly line balancing problem assumes that the manufacturing methods to be used have been predetermined. However, in practice the design engineer has several alternatives available in the choice of processing, typically involving a trade-off between labor or...

  • A new approach for cell formation and scheduling with assembly operations and product structure. Aryanezhad, M. B.; Aliabadi, Jamal; Tavakkoli-Moghaddam, Reza // International Journal of Industrial Engineering Computations;Jul2011, Vol. 2 Issue 3, p533 

    In this paper, a new formulation model for cellular manufacturing system (CMS) design problem is proposed. The proposed model of this paper considers assembly operations and product structure so that it includes the scheduling problem with the formation of manufacturing cells, simultaneously....

  • Multi-objective approaches to balance mixed-model assembly lines for model mixes having precedence conflicts and duplicable common tasks. Kara, Yakup; Özgüven, Cemal; Seçme, Neşe; Chang, Ching-Ter // International Journal of Advanced Manufacturing Technology;Feb2011, Vol. 52 Issue 5-8, p725 

    The existence of common tasks for model mixes is the main characteristic of the mixed-model assembly lines. The decision problem considered in this study is how some common tasks can be duplicated to improve the efficiency of a mixed-model assembly line under the assumption that some of the...

  • Fast load balancing with the most to least loaded policy in dynamic networks. Sider, Abderrahmane; Couturier, Raphaël // Journal of Supercomputing;Sep2009, Vol. 49 Issue 3, p291 

    Load balancing a distributed/parallel system consists in allocating work (load) to its processors so that they have to process approximately the same amount of work or amounts in relation with their computation power. In this paper, we present a new distributed algorithm that implements the Most...

  • Efficient deadlock prevention policy in automated manufacturing systems using exhausted resources. Hu, Hesuan; Li, Zhiwu // International Journal of Advanced Manufacturing Technology;Mar2009, Vol. 40 Issue 5/6, p566 

    To design supervisors enforcing liveness of automated manufacturing systems (AMS), an efficient deadlock prevention policy based on the exhausted resources is proposed. This policy exploits a special structure of Petri nets in the sense that the liveness of a specific system can be guaranteed if...

  • Batch sequencing and cooperation. Çiftçi, Barış; Borm, Peter; Hamers, Herbert; Slikker, Marco // Journal of Scheduling;Aug2013, Vol. 16 Issue 4, p405 

    Game theoretic analysis of sequencing situations has been restricted to manufacturing systems which consist of machines that can process only one job at a time. However, in many manufacturing systems, operations are carried out by batch machines which can simultaneously process multiple jobs....


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics