Scheduling unit processing time jobs on an m -machine flow-shop
- PDF / 143,573 Bytes
- 5 Pages / 595 x 794 pts Page_size
- 62 Downloads / 170 Views
r 2003 Operational Research Society Ltd. All rights reserved. 0160-5682/03 $25.00 www.palgrave-journals.com/jors
Scheduling unit processing time jobs on an m-machine flow-shop G Mosheiov* The Hebrew University, Jerusalem, Israel The sequential production of identical jobs and the flow-shop machine setting are extremely common in real-life applications. We study a scheduling problem that combines these two elements: jobs of identical processing time, with job-dependent weights, and a given common due date processed on an m-machine flow-shop. The (just-in-time) objective is to minimize the maximum earliness/tardiness cost. We introduce a polynomial time solution in both cases of (i) a non-restrictive (ie, sufficiently large) due date, and (ii) a restrictive due date (which restricts the number of early jobs). Journal of the Operational Research Society (2003) 54, 437–441. doi:10.1057/palgrave.jors.2601512 Keywords: scheduling; flow-shop; just-in-time
Introduction Sung and Min1 studied a scheduling problem that combines a flow-shop machine setting and a just-in-time (JIT) objective. Specifically, they addressed a two-machine flowshop problem where jobs need to be completed as close as possible to a common due date. In all four cases analyzed and solved in their study, the objective was of a minsum type, that is, minimizing the sum of the earliness/tardiness costs incurred for all of the jobs. Both flow-shop scheduling and JIT scheduling are very popular topics among researchers. It is therefore somewhat surprising that so few papers combining these topics have been published. In this note, we study a related problem consisting, again, of a JIT objective in a flow-shop machine environment. Like Sung and Min,1 we consider a common due date, where jobs completed prior to (after) the due date are penalized according to their earliness (tardiness) value. However, unlike their model, we assume a minmax objective, that is, the cost of a schedule is determined by the largest cost incurred for any of the jobs. Several papers have addressed scheduling problems with a minmax objective in a JIT setting. Sidney,2 Garey et al3 and Li et al 4 studied single-machine and job-dependent due dates. Cheng and Chen,5 Li and Cheng6 and Federgruen and Mosheiov7 studied the parallel machine setting with different assumptions on the cost structure. Excluding several special cases, all these problems were shown to be NP-hard. Thus, most of these studies presented complexity results and introduced and analyzed heuristic algorithms. Mosheiov and
*Correspondence: G Mosheiov, School of Business Administration, The Hebrew University, Jerusalem 91905, Israel. Email: msomer@ mscc.huji.ac.il
Shadmon8 focused on the special case of unit processing time jobs. This very practical setting includes the common case of identical products, which are assumed (after an appropriate normalization) to have unit processing times. They studied both settings of single-machine and of parallel identical machines under different assumptions regarding the restrictiveness of the c
Data Loading...
