The just-in-time scheduling problem in a flow-shop scheduling system

Dvir Shabtay

European Journal of Operational Research, 2012, vol. 216, issue 3, 521-532

Abstract: We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n3) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n3) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(nlogn) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn2) time optimization algorithm.

Keywords: Just-in-time scheduling; Flow-shop; Complexity; Pseudo-polynomial time algorithm; No-wait restriction (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221711006850
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:216:y:2012:i:3:p:521-532

DOI: 10.1016/j.ejor.2011.07.053

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().